重念一次早該補起來的「資料結構與演算法」。這篇筆記下 B＋Tree 與 Database 的運用。
![[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74](https://smlpoints.com/wp-content/uploads/notes-theideaofalgorithm-javascript-1.jpg "[筆記] 程式必修課！資料結構與演算法｜JavaScript 篇 – 74")
課程相關資訊
[連結]：https://hiskio.com/en/courses/572/lectures/146357
本篇範圍：Chapter 14
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
1. 由於資料庫的大小量體遠比 RAM 大的多，故 BST ( Binary Search Tree ) 並不適合用在資料庫
2. 藉由在一個 Node 裡存放更多資料，可以有效減少 Disk I/O 的讀寫次數來找資料
3. 一般常見的 Disk I/O page size 是 4096 bytes
4. B-Tree 的搜尋一致性不夠高，在越接近 root 的 node，其速度會比底層快很多；此外搜尋會經常需要遍利多個節點，才能確保找齊所有資料
5. B+Tree 在 B-Tree 的規則上，額外加上以下三個規則
A. 沒有子樹或是子節點的 non-leaf 節點，僅儲存其 pointer
B. 僅 leaf node 存資料
C. leaf node 彼此間用 linked List 串聯
