B樹，B+樹，B*樹

下面我們來詳細講解一下?B樹、B+樹、B*樹?這三種非常重要的多路平衡查找樹。它們在數據庫和文件系統中有著極其廣泛的應用。

一、為什么需要這些樹結構？

在開始之前，我們先思考一個問題：為什么已經有了二叉搜索樹（BST）、AVL樹、紅黑樹，還需要B樹家族？

答案是：磁盤I/O。

內存訪問：速度極快，納秒級別。
磁盤訪問：速度極慢，毫秒級別，比內存慢了幾個數量級。

操作系統從磁盤讀取數據時，并不是按需一個字節一個字節地讀，而是以頁（Page，通常為4KB或8KB）為單位進行預讀。一次I/O操作會把一整頁的數據都加載到內存中。

傳統的二叉樹（如紅黑樹）雖然內存中效率很高，但每個節點只存儲少量數據，如果數據量巨大，樹會變得很高。查詢一個數據可能需要從根節點訪問到葉子節點，這期間可能發生很多次磁盤I/O（因為節點可能不在同一頁），性能會急劇下降。

B樹家族的設計目標就是為了減少磁盤I/O次數。它們的核心思想是：

一個節點 = 一個磁盤頁
通過在每個節點中存儲更多的鍵和指針，讓樹變得更“矮胖”，從而降低樹的高度，減少查詢時的I/O次數。

二、B樹 (B-Tree)

B樹是一種自平衡的多路搜索樹，它不是二叉的，一個節點可以有多個子節點。

1. 結構特點

平衡性：所有葉子節點都位于同一層，保證了查詢性能的穩定。
多路性：一個節點可以擁有多于兩個的子節點。這通常用“階”（m）來定義。一棵m階的B樹滿足以下條件：
- 每個節點最多有?m?個子節點。
- 除根節點和葉子節點外，每個節點至少有?ceil(m/2)?個子節點（ceil是向上取整）。
- 根節點至少有2個子節點（除非它同時也是葉子節點）。
- 所有葉子節點都在同一層。
- 一個有?k?個子節點的非葉子節點，包含?k-1?個鍵（Key）。
- 節點中的鍵是有序的。

2. 節點結構

一個典型的B樹節點包含：

n?個鍵?K?, K?, ..., K?。
n+1?個指針?P?, P?, ..., P?。
指針指向子節點，鍵和指針的排列滿足：P?指向的子樹中所有鍵 <?K??<?P?指向的子樹中所有鍵 <?K??< … <?K??<?P?指向的子樹中所有鍵。

示例（3階B樹，也叫2-3樹）：

        [ 20 | 40 ]/     |     \[10, 15] [30, 35] [50, 60]

每個節點最多有3個子節點，至少有2個子節點。
每個節點最多有2個鍵，至少有1個鍵。

3. 操作

查找：從根節點開始，將待查找的鍵與節點中的鍵比較，確定下一步要進入哪個子樹，直到找到或到達葉子節點。
插入：找到合適的葉子節點插入。如果插入后節點鍵的數量超過?m-1，則節點分裂。中間的鍵向上提升到父節點，如果父節點也滿了，則繼續向上分裂，可能一直到根節點。
刪除：比較復雜，可能需要從兄弟節點“借”鍵，或者與兄弟節點合并，甚至可能導致父節點的合并，是一個遞歸的過程。

4. 優缺點

優點：
- 矮胖，樹的高度低，I/O次數少，非常適合磁盤存儲。
- 查詢、插入、刪除的時間復雜度都為?O(log?N)，其中N是鍵的數量，m是階數。
缺點：
- 每個節點都存儲了鍵和數據（如果數據很大，節點能存的鍵就變少了，樹會變高）。
- 范圍查詢效率不高，因為數據分散在所有節點中，需要進行中序遍歷，這會涉及大量的隨機I/O。

三、B+樹 (B+ Tree)

B+樹是B樹的變種，也是目前數據庫索引中最常用的數據結構（如MySQL的InnoDB引擎）。它對B樹做了優化，使其更適合范圍查詢和全表掃描。

1. 結構特點（與B樹的區別）

B+樹在B樹的基礎上增加了以下特性：

數據只在葉子節點：
- 非葉子節點（索引節點）：只存儲鍵和指向子節點的指針，不存儲數據。這使得非葉子節點可以存儲更多的鍵，樹的結構更“矮胖”，I/O效率更高。
- 葉子節點（數據節點）：存儲了所有的鍵和對應的數據。
葉子節點形成有序鏈表：
- 所有的葉子節點通過指針連接成一個雙向有序鏈表。
- 這使得范圍查詢變得極其高效，只需定位到范圍的起始點，然后沿著鏈表順序遍歷即可，幾乎都是順序I/O。
查詢效率更穩定：
- 任何查詢都必須從根節點走到葉子節點才能獲取到數據。而B樹可能在非葉子節點就命中數據。這使得B+樹的每次查詢的I/O次數更加穩定。

2. 圖示

        [ 20 | 40 ]/     |     \[ 10 ]   [ 30 ]   [ 50 ]/         |         \
[10, Data] [30, Data] [50, Data]<--------> <--------> <--------> (雙向鏈表)

上面的非葉子節點只做索引，不存數據。
下面的葉子節點存數據，并且用鏈表連接。

3. 優缺點

優點：
- 更矮胖：由于非葉子節點不存數據，能容納更多鍵，樹高更低，I/O次數更少。
- 查詢性能穩定：每次查詢都必須查到葉子節點，性能穩定。
- 范圍查詢極其高效：葉子節點的有序鏈表結構，使得范圍查詢和排序操作非常快。
- 全表掃描快：只需遍歷葉子節點的鏈表即可。
缺點：
- 單點查詢（根據主鍵查一條記錄）可能比B樹稍慢，因為B樹可能在非葉子節點就找到數據，而B+樹必須走到葉子節點。但在實際應用中，由于B+樹更矮胖，這個劣勢通常不明顯，甚至可能更快。

四、B樹 (B Tree)

B*樹是B樹的另一個變種，它的目標是進一步提高節點的空間利用率。

1. 結構特點（與B樹的區別）

B*樹的核心思想是增加節點的填充率，從而減少節點分裂的頻率。

更高的填充因子：
- B樹要求每個非根、非葉節點至少半滿（ceil(m/2)）。
- B*樹要求每個非根、非葉節點至少?2/3滿（ceil(2m/3)）。
獨特的分裂策略：
- 當一個節點滿了需要插入新數據時，B*樹不會立即分裂。
- 它會先檢查其相鄰的兄弟節點是否還有空間。
- 如果兄弟節點未滿：將當前節點和兄弟節點的鍵重新分配，讓兩個節點都達到2/3滿。這個過程稱為節點重分配。
- 如果兄弟節點也滿了：才會進行分裂。但B*樹的分裂也與B樹不同。它不是將一個節點分成兩個，而是將當前節點和它的一個兄弟節點一起分裂成三個節點，并保證這三個節點都是2/3滿的。

2. 優缺點

優點：
- 極高的空間利用率：由于2/3的填充因子和延遲分裂策略，節點的空間利用率非常高，浪費的空間很少。
- 更少的分裂操作：節點重分配和“分裂成三”的策略大大降低了節點分裂的頻率，從而減少了I/O操作，提高了插入性能。
缺點：
- 實現復雜：插入和刪除的邏輯比B樹和B+樹復雜得多，需要處理節點重分配和復雜的分裂邏輯。
- 應用較少：由于其復雜性，B*樹在實際應用中不如B+樹普及。但在一些對空間利用率和插入性能要求極高的文件系統中，可能會看到它的身影。

總結與對比

特性	B樹	B+樹	B*樹
數據存儲位置	所有節點（鍵+數據）	僅葉子節點（鍵+數據）	僅葉子節點（鍵+數據）
非葉子節點作用	索引+數據	僅索引	僅索引
葉子節點結構	獨立，無連接	雙向有序鏈表	雙向有序鏈表
查詢性能	不穩定（可能在非葉子節點命中）	穩定（必須到葉子節點）	穩定（必須到葉子節點）
范圍查詢	效率低（中序遍歷，隨機I/O）	效率極高（鏈表順序遍歷）	效率極高（鏈表順序遍歷）
節點填充率	至少半滿 (`ceil(m/2)`)	至少半滿 (`ceil(m/2)`)	至少2/3滿?(`ceil(2m/3)`)
分裂策略	節點滿則分裂成兩個	節點滿則分裂成兩個	先嘗試與兄弟節點重分配，失敗則分裂成三個
空間利用率	一般	較高	非常高
實現復雜度	中等	中等	高
主要應用	文件系統（如HFS+, NTFS部分）	數據庫索引（MySQL, Oracle）	少數文件系統，對空間利用率要求高的場景