B-tree（平衡多路查找樹）是自平衡樹的數據結構，維護已排序的數據。關于二叉樹和其它自平衡樹可查看上篇每次面試都會被問到，什麼是紅黑樹？。

一棵階的樹滿足以下性質，

1. 每個節點最多有個子節點。
2. 如果根不是葉節點，則根至少有兩個子節點。
3. 每個非葉節點（根除外）至少有 個子節點。
4. 具有 個子節點的非葉節點包含 個鍵。
5. 所有的葉子節點都具有相同的高度。

每個非内部節點的鍵充當分隔其子樹的分隔值。例如，下面是一棵 5 階樹的片段，内部節點有包含兩個鍵 [7, 16] ，所以它有三個子節點，最左邊子節點的鍵滿足小于7，中間子節點的鍵滿足大于7小于16，最右邊子節點的鍵滿足大于16。

内部節點：内部節點是除葉節點和根節點之外的所有節點。

B-tree

場景

B-tree 跟 紅黑樹應用場景不同，這種數據結構是為了處理大量數據而發明，它針對讀寫大數據量系統進行優化，常用于數據庫和文件系統。

紅黑樹常用在應用程序，因為它處理的數據量一般不超過主存(RAM)容量。在數據庫場景中，數據量都是GB，TB級别，數據存儲在磁盤上，每次操作需要訪問磁盤讀取數據。

計算機存儲硬件中訪問數據的時間從快到慢依次如下：

• 寄存器
• CPU緩存（L1、L2 和 L3）
• 主内存（RAM）
• 磁盤驅動器（固态磁盤）
• 磁盤驅動器（磁盤）

執行典型指令 　　　　　　　　　　 1/1000000000 秒 = 1納秒 從一級緩存中讀取數據 　　　 　　　　 0.5 納秒 從二級緩存中讀取數據 　　　　　　　 7 納秒 從主内存中讀取數據 　　 　　　　 100 納秒 從新的磁盤位置讀取數據 　　 8000000 納秒 = 8毫秒

從上面可以看出，主内存的訪問時間在納秒級别，磁盤訪問時間在毫秒級别。這意味着如果程序從磁盤讀取會比從主内存讀取慢 100, 000 倍。

所以 B-tree 優化目的就是減少磁盤訪問次數，通過下面方式：

• 降低樹高度，使用多叉樹結構，讓單個節點存儲更多個鍵。
• 數據以塊讀取，這樣一次可以讀取更多數據，一般來說節點容量等于磁盤塊大小。

1秒=1000毫秒=1000000微秒=1000000000納秒

自平衡

拆分樹節點

下面是一個 6階B-tree（m=6），它一個節點可以擁有的最大鍵數是5，當插入數字6時，左邊節點到達最大鍵，需要拆分樹的節點。

插入新數字6 步驟如下：

1. 先求出節點的中位數為 3；
2. 創建一個新的葉節點，将中位數 3 之後的所有鍵複制到新節點；
3. 将中位數3 上移，插入到父節點适當位置；
4. 在中位數3 後添加一個父節點到新節點的指針；
5. 将新數字 6 添加到新節點的正确位置。

合并樹的兩個節點

删除鍵後，如果節點鍵數量小于最小鍵數時需要合并節點。下面樹一個節點可以擁有的最小鍵數為2。

删除葉節點鍵1：

1. 查找到1删除；
2. 删除3左指針，将 2 複制到 [4，5]節點，3下移；
3. 3下移後，隻有一個鍵6，父節點繼續下移，直到平衡。

删除内部節點20：

1. 查找到 20 删除，選取 20位置左子節點中最大值19 替換；
2. 删除 19位置左指針；
3. 17 鍵下移到 [15,16]節點，18追加到後面。

B tree

B tree 是 B-tree 一個優化版本，用于數據庫索引。B tree與B-tree的區别主要有兩個方面：

• B tree非葉子節點隻存儲鍵，而B-tree所有節點都可以存儲鍵值；
• B tree 鍵對應的值都存儲在葉節點并且通過鍊表鍊接在一起。

下圖展示了B tree存儲鍵值的情況，鍵 [1-7] 對應的值 [d1-d7]。

B tree

MySQL存儲引擎 InnoDB中的 B tree

MySQL 創建表時會生成一個 .ibd文件，這個ibd文件是一個功能齊全的空間。每個空間又被拆分成多個頁面(Page)，每一頁都會分配了一個 32 位整數頁号，每個頁面大小通常為16kB。

B tree 索引中每個節點容量一個頁面的大小，葉子節點和非葉子節點數據類型不同。

葉子節點包含鍵值和下一條記錄的指針。

B_Tree_Simplified_Leaf_Page

非葉子節點包含子頁面的頁碼和指向的子頁面的最小鍵。

B_Tree_Simplified_Non_Leaf_Page

同級節點之間，每個節點上一頁和下一頁的指針，形成同一級别頁面的雙向鍊表。

B_Tree_Simplified_Level

綜上索引結構如下，同級頁面形成雙向鍊接，在每個頁面内記錄升序鍊接，非葉頁面包含子頁面“指針”（子頁碼）。

B_Tree_Structure

關于B tree 效率問題，可以查看下表

樹高度	非葉頁面	葉子頁面	行數	大小
1	0	1	468	16.0 KB
2	1	1203	> 56.3 萬	18.8 MB
3	1204	1447209	> 6.77 億	22.1 GB
4	1448413	1740992427	> 8140 億	25.9 TB

大多數表索引高度再1-3級，所以一般隻需要1-3次磁盤IO操作就可以完成。上面圖中描述的都是聚集索引（主鍵）。

數據庫中的 B Tree索引分為聚集索引（clustered index）和次要索引（secondary index），聚集索引的葉子頁是包含整行數據的頁面，次要索引的葉子頁存儲了對應行的主鍵。

• 使用聚集索引查詢可以直接獲得整行數據。
• 使用次要索引查詢時，先查詢到主鍵值，然後再通過主鍵在聚集索引中找到完整的行數據。

小結

B-tree 是一種大數據量場景下的優化數據結構，旨在減少磁盤訪問次數（降低樹高度）。

B-tree 中的著名版本 B tree 通過讓非葉節點隻存儲鍵，占用空間變小，使得每一層節點可以索引更多數據，有效控制了樹高度。

MYSQL的InnoDB中使用 B tree 作為索引，正常情況下樹高度保持在 1-4 級。

,