B-tree 靠一個節點放多個鍵把樹壓矮，換到更少的讀取次數

索引是一個排序過的資料結構，裡面帶著指向資料的 pointer。沒有索引時搜尋只能 linear search，時間複雜度 O(n)；建了 B+ tree 索引之後是 O(log N)。

換成二元搜尋樹，百萬筆資料只要讀 20 次左右就找得到。那還能再更少嗎？——1971 年 Rudolf Bayer 與 Edward M. McCreight 提出的 B-tree 就是在回答這題。

方法：一個節點不只放一個鍵

B-tree 的特點是每個節點都有多個鍵，而不是一個。鍵變多 → 分支變多 → 同樣的資料量，樹的層數變少。

資料 1~100	層數	最多讀幾次
平衡二元搜尋樹	至少 7 層	7
B-tree（每個節點最多 10 個鍵）	3 層	3

搜尋要讀幾次 = 樹有幾層。 把樹壓矮，就是直接減少讀取次數——這就是選 B-tree／B+ tree 而不是二元搜尋樹的理由。

（可以在 https://btree.app/ 動手建一棵試試。）

代價

建索引要額外的記憶體／儲存空間，所以建之前要評估：寫大於讀的情況就不適合建——這筆交易的完整帳見 索引是拿寫入換查詢，寫多讀少的表加索引是純虧。

相關：全表掃描和索引掃描的適用場景是相反的（沒有索引時就是那個 O(n)）