【數據結構】B+ 樹——高度近似于菌絲網絡—

文章目錄

B+ 樹的定義
B+ 樹組織數據的方法
- 往 B+ 樹中插入鍵值對數據
- 從 B+ 樹中刪除鍵值對
把 B+ 樹看作是 “真菌網絡”——我理解并記憶 B+ 樹的方法
B+ 樹的 C 代碼實現
- 初始化節點、B+ 樹
- B+ 樹節點內的二分查找
- B+ 樹的數據插入操作
- B+ 樹的刪除數據操作
- 范圍查詢與全局遍歷
- 銷毀 B+ 樹
- 測試代碼（主函數）

推薦一個零聲教育學習教程，個人覺得老師講得不錯，分享給大家：[Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK等技術內容，點擊立即學習: https://github.com/0voice 鏈接。

B+ 樹的定義

B+ 樹與 B樹是有一定的相似性，大家可以參考這篇文章。

B+ 樹是一個針對單個有序的索引指標的數據列（鍵值對型的數據列 ）的高效查詢算法，它提供了一個組織數據的方法，按照這個方法先行組織數據，而后能高效率的對某個索引鍵的數據進行查詢，而后實現快速的范圍查詢。

對比發現，紅黑樹是無法實現范圍查詢，即對某一個范圍內的鍵值進行數據查詢。SPLAY 樹和 B 樹都能實現范圍查詢。這些 “樹算法” 的搜索方法原理都是一樣的，通過讓查詢鍵和節點的各個鍵比大小，從而確定查詢的路徑。不同于前面所例舉的 “樹”，B+ 樹是需要一直查到葉結點處，才能獲取具體數據。

🌲 B+樹與紅黑樹的核心差別

特性	紅黑樹 (Red-Black Tree)	B+ 樹 (B+ Tree)	本質差異
類型	二叉平衡搜索樹 (每個節點最多2個子節點)	多路平衡搜索樹 (每個節點有多個子節點，m階)	節點分支數：二叉 vs 多路
平衡性	通過顏色和旋轉規則保持大致平衡 (非絕對完美)	通過節點分裂/合并保持絕對平衡 (所有葉子同層)	平衡嚴格性：紅黑樹高度上限 2log?(n+1)， B+樹更矮胖 (log?n, m>>2)
節點內容	每個節點存儲：1. 鍵；2. 數據指針；3. 左右子節點指針；4. 顏色標記	內部節點：只存鍵 + 子節點指針。//////// 葉子節點：存鍵 + 數據指針 + 指向下一個葉子的指針	數據位置：紅黑樹數據分散在所有節點；B+樹數據僅存于葉子，內部節點純路由
范圍查詢效率	中序遍歷 (O(n)，但需遍歷整棵樹，內存跳躍訪問，緩存不友好)	葉子節點鏈表順序遍歷 (O(n)，但連續內存訪問，緩存極友好)	范圍查詢性能：B+樹碾壓式優勢 (鏈表連續訪問 vs 樹的遞歸遍歷)
樹高	相對較高 (O(log?n))	相對極矮 (O(log?n), m 通常數百)	訪問局部性：B+樹單節點載入大量鍵，減少I/O (對磁盤關鍵)
主要設計目標	內存內高效操作 (插入/刪除/查找 O(log?n))	減少磁盤I/O次數 (樹矮，節點匹配磁盤塊大小)	優化方向：紅黑樹優化CPU計算；B+樹優化磁盤I/O
適用存儲	內存 (RAM)	磁盤/SSD (輔存)	主戰場不同：內存 vs 外存

我們常說的 B+ 樹，通常都是說 “ m 階的 B+ 樹 ” ，即每一個節點都不能有超過 m-1 個鍵，不超過 m 個子節點（那也就是說共 $2 m ? 1$ 項內容）。B+ 樹有 8 條定義律：

內部節點：
– 存儲 k 個路由鍵（ $? m /2 ? ? 1 \leq k \leq m ? 1$ ）
–包含 k+1 個子節點指針
–不存儲任何數據指針
葉子節點：
–存儲 k 個鍵值對（ $? m /2 ? ? 1 \leq k \leq m ? 1$ ）
–包含 k 個數據指針
–包含指向下一個葉子節點的指針
所有葉子節點必須位于同一深度
–從根到任意葉子的路徑長度相等
–樹完全平衡
鍵值繼承原則：
–內部節點的鍵 $K_i = 其對應子樹的最小鍵$
–即： $K_i = \min(children[i+1])$
路由鍵范圍劃分：
–對任意內部節點鍵 K_i：
– 子節點 $children[i] 中所有鍵 ≤ K_i$
– 子節點 $children[i+1] 中所有鍵 > K_i$
數據位置限定：
– 實際數據只存儲在葉子節點
– 內部節點僅包含路由信息
– 葉子節點包含完整鍵集合
葉子節點必須按鍵順序組成單向鏈表
– 通過 next 指針連接
– 鏈表按鍵升序排列
當根節點作為中間節點而存在時，它是一個特殊的中間節點（構成性的例外），它可以僅擁有一個鍵，兩個子節點。這樣能為算法在不斷插入新節點的時候，節點不斷地在分裂和上溢時，更新 B+ 樹的同時，作定義上的兜底。

節點類型	鍵數量范圍	指針數量	存儲內容
根節點	1 ≤ k ≤ m-1	k+1	路由鍵+子節點指針
內部節點	?m/2?-1 ≤ k ≤ m-1	k+1	路由鍵+子節點指針
葉子節點	?m/2?-1 ≤ k ≤ m-1	k	鍵+數據指針

根據以上定義，我們以 4 階 B+ 樹為例，具體解釋這些定義條的作用。 每個節點至多擁有 $3 ? 1 = 2$ 個鍵，至多 3 個指針。我們可以想象它的中間節點是長這樣的，2 個鍵，鍵是某個具體數據塊的索引 key，key 是可以用來與查詢鍵比大小而后查詢出數據的具體位置，從哪條通路走下去；3 個路由指針，每個路由指針指向字節點的地址，這就是導引查詢數據的通路。

┌------------------------------------┐
│ 指針0 │ 鍵K? │ 指針1 │ 鍵K? │ 指針2   │
└------------------------------------┘

葉子節點是長這樣的，他和中間節點一樣，共有 3 個指針，3 個鍵。鍵是具體數據塊本身的索引 key，其中的 2 個指針是具體數據塊的指針，1 個指針是指向下一個葉子節點的指針。

┌-----------------------------------------┐
│ 鍵K?:數據指針 │ 鍵K?:數據指針 │ next指針    │
└-----------------------------------------┘

3 階 B+ 樹的葉子節點和中間節點的關系則如下所示

_____________中間節點_________________┌------------------------------------┐│ 指針0 │ 鍵K3 │ 指針1 │ 鍵K5 │ 指針2 │└------------------------------------┘/             |                 |______________________________________________/              |                 |_______________|                                                _____________|                                 |\|/                                              /                                               |_|_                                           _\|/_                                            _\|/_
┌-----------------------------------------┐       ┌-----------------------------------------┐       ┌-----------------------------------------┐
│ 鍵K1:數據指針 │ 鍵K2:數據指針 │ 葉子2 的指針 │       │ 鍵K3:數據指針 │ 鍵K4:數據指針 │ 葉子3 的指針 │       │ 鍵K5:數據指針 │ 鍵K6:數據指針 │ 葉子4 的指針 │
└-----------------------------------------┘       └-----------------------------------------┘       └-----------------------------------------┘
______________葉子節點 1__________________        _______________ 葉子節點 2__________________       ________________葉子節點 3__________________

B+ 樹組織數據的方法

只有合理的組織數據，才會有高效率的查詢。所謂的 ‘’組織數據“ ，就是插入鍵值對數據（注意，這不是插入節點！原因是一個節點有可能會有好幾份數據。）以及刪除鍵值對數據。

下面我將以 4 階的 B+ 樹為例，去介紹其數據插入和數據刪除。

葉子節點的形式約定如下。 A 代表 32 鍵的 value，B 代表 46 鍵的 value，“–>” 代表指向下一個葉子節點的指針。

+-+--+-+--+---+
|A|32|B|46|-->|
+-+--+-+--+---+

中間節點、根節點的形式約定是，空白間隔條就是 “路由指針”，走向下一層的節點。

++--++--++
||32||46||
++--++--++

往 B+ 樹中插入鍵值對數據

是插入鍵值對數據，而非插入節點！原因是一個節點有可能會有好幾份數據。

情況一：根節點滿員導致的節點分裂，鍵信息上溢（注意數據 value 并沒上傳）。至于葉子節點的分裂也是類似的。我們需要注意到的是不同層的中間節點的鍵是可以重復的。

增加鍵 50 與 D 值 
+-+--+-+--+-+--+---+
|A|32|B|46|C|47|-->|
+-+--+-+--+-+--+---+節點滿員了，需要鍵的上溢，與節點分裂+-+--+-+--+-+--+-+--+---+|A|32|B|46|C|47|D|50|-->|+-+--+-+--+-+--+-+--+---+++--++||47||++--++/     \/       \/           \
+-+--+-+--+---+         +-+--+-+--+---+
|A|32|B|46|-->|         |C|47|D|50|-->|
+-+--+-+--+---+         +-+--+-+--+---+

情況二：已滿員的中間節點插入數據，導致節點分裂，我們需要注意到的是不同層的中間節點的鍵是可以重復的。

插入一個 45 的新鍵++--++--++||33||49||++--++--++/   |    \__/    |     \__/		|         \/         |          \
++--++--++  ++--++--++--++  ++--++--++
||25||30||  ||33||43||44||  ||49||50||
++--++--++  ++--++--++--++  ++--++--++
發現節點數據超員了，進行節點分裂++--++--++||32||46||++--++--++/   |    \__/    |     \_________/		|               \/         |                \
++--++--++  ++--++--++--++--++  ++--++--++
||25||30||  ||33||43||44||45||  ||49||50||
++--++--++  ++--++--++--++--++  ++--++--++節點數據平分兩份，中間的 44 鍵上傳++--++--++--++||32||44||46||++--++--++--++/   |    |	\__/    |    | 	 \_________/		|     \             \/         |       \            \
++--++--++  ++--++--++  ++--++--++  ++--++--++
||25||30||  ||33||43||  ||44||45||  ||49||50||
++--++--++  ++--++--++  ++--++--++  ++--++--++

情況三：中間節點的節點正常插入和葉子節點的正常插入，就不展示了。

從 B+ 樹中刪除鍵值對

是刪除鍵值對數據，而非刪除節點！原因是一個節點有可能會有好幾份數據。

情況一：葉子節點的刪除數據，發現刪除之后低于半數，向兄弟節點借數據。（中間節點的數據刪除也是類似的）。會連帶的把上面帶有 33 的鍵的節點進行數據刪除（遞歸式的刪除）。

刪除數據 33 ++--++--++||33||47||++--++--++/   |    \__/     \     \____/		 |           \/           \            \
+-+--+-+--+---+    +-+--+---+  +-+--+-+--+---+
|A|25|B|30|-->|    |C|33|-->|  |D|47|E|50|-->|
+-+--+-+--+---+    +-+--+---+  +-+--+-+--+---+向兄弟節點借數據，先抵押給父節點++--++--++||32||47||++--++--++/   |    \__/     \     \____/		 |           \/           \            \
+-+--+-+--+---+                +-+--+-+--+---+
|A|25|B|30|-->|                |D|47|E|50|-->|
+-+--+-+--+---+                +-+--+-+--+---+父節點換數據，再進行數據下滲++--++--++||30||47||++--++--++/   |    \__/     \     \____/		 |           \/           \            \
+-+--+---+    +-+--+---+  +-+--+-+--+---+
|A|25|-->|    |B|30|-->|  |D|47|E|50|-->|
+-+--+---+    +-+--+---+  +-+--+-+--+---+

情況二：葉子節點的刪除數據，發現刪除之后低于半數，而且兄弟節點數據剛好在半數，也無法借出數據。（中間節點的數據刪除也是類似的）。會連帶的把上面帶有 33 的鍵的節點進行數據刪除（遞歸式的刪除）。故而只好合并節點。

刪除鍵為 30 的節點++--++--++||30||47||++--++--++/   |    \__/     \     \____/		 |           \/           \            \
+-+--+---+    +-+--+---+  +-+--+---+
|A|25|-->|    |B|30|-->|  |D|47|-->|
+-+--+---+    +-+--+---+  +-+--+---+
節點合并++--++--++||30||47||++--++--++/   |    \__/     \     \____/		 |           \/           \            \
+-+--+---+                  +-+--+---+
|A|25|-->|                  |D|47|-->|
+-+--+---+                  +-+--+---+++--++||47||++--++/    \__/      \____/	            \/                  \
+-+--+---+               +-+--+---+
|A|25|-->|               |D|47|-->|
+-+--+---+               +-+--+---+

情況三：正常的中間節點刪除、葉子節點刪除數據，就不羅列了。

把 B+ 樹看作是 “真菌網絡”——我理解并記憶 B+ 樹的方法

在這里插入圖片描述

🍄 B+樹的真菌生長比喻
想象一片數字森林，其中生長著一種名為 B+ 菌的神奇真菌：

孢子萌發（初始狀態）
1、森林中誕生一個初始孢子細胞（根節點兼葉子節點）
2、這個細胞通過吸收數據養分（插入鍵值對）逐漸長大
質配階段（節點填充）
1、細胞通過菌絲網絡（指針）與其他細胞交換遺傳物質（鍵值傳遞）
2、細胞膜（節點容量）不斷擴張，容納更多染色體片段（鍵值對）
3、當細胞達到臨界質量（階數M）時，進入減數分裂準備期
減數分裂（節點分裂）
1、細胞核發生均等裂變（鍵值均勻分裂）
2、產生兩個子細胞（新葉子節點）
3、關鍵染色體（最小鍵K3）通過菌絲管道提升到上層細胞（父節點）
菌絲網絡形成（葉子鏈表）
1、子細胞間分泌信息素導管（next指針）
2、形成地下菌絲網絡（葉子節點鏈表）
3、養分（數據）可通過網絡連續輸送（范圍查詢）
子實體發育（樹結構生長）
1、當上層細胞也達到臨界質量時，觸發級聯分裂
2、最終在森林地表形成：
3、菌蓋（根節點）：指揮中心
4、菌褶（內部節點）：傳輸通道
5、菌絲體（葉子鏈表）：營養交換網絡

B+ 樹的 C 代碼實現

我們需要明確的一點是
$數據結構 = 數據定義 + 數據的操作方法。$

首先是數據定義。

// B+樹階數 - 每個節點最多M-1個鍵，M個孩子
#define M 4
#define MIN_KEYS ((M) / 2)// B+樹節點結構
typedef struct BPlusTreeNode {bool is_leaf;           // 是否為葉子節點int key_count;          // 當前鍵的數量int keys[M];            // 鍵數組union {struct BPlusTreeNode* children[M + 1]; // 內部節點的子節點指針void* data_ptrs[M]; // 葉子節點的數據指針};struct BPlusTreeNode* next; // 葉子節點的鏈表指針
} BPlusTreeNode;// B+樹結構
typedef struct {BPlusTreeNode* root;
} BPlusTree;

B+ 樹的數據結構

葉子節點 leaf 和中間節點 internal 還是是有區分的。在范圍查詢上，葉子節點的鏈表指針提供了便利；葉子節點負責儲存數據；
理論上，葉子節點和中間節點都有 M+1 （階）個指針，只是葉子節點有 M 個數據指針和 1 個葉子鏈表指針，而中間節點有 M+1 個路由指針。
但實際上，路由指針數組的指針和數據指針被統一在聯合體中，降低了節點的內存，葉子和中間點都可以共用同一個數據結構。
key_count、0 和 MIN_KEYS 是三個重要的數字，在節點合并、節點分裂、借兄弟數據、葉子刪數據和葉子加數據都有涉及。
所有節點都有最多有 M 個鍵，它們是 M+1 階的。第 K 個鍵大于第 K 個路由指針下的任何一個鍵，第 K 個鍵小于等于第 K+1 個路由指針下的任何一個鍵。父節點的第 K 個鍵等于第 K+1 個子節點的第 0 個鍵

初始化節點、B+ 樹

// 創建新節點
BPlusTreeNode* create_node(bool is_leaf) {BPlusTreeNode* node = (BPlusTreeNode*)malloc(sizeof(BPlusTreeNode));node->is_leaf = is_leaf;node->key_count = 0;//  務必要注意，節點的所有 key 一定要初始化成一個不會與所插入鍵重復的值，否則很麻煩。node->next = NULL;for (int i = 0; i < M; i++) {node->keys[i] = INT_MAX; // 初始化為最大值}return node;
}// 初始化B+樹
BPlusTree* init_bplus_tree() {BPlusTree* tree = (BPlusTree*)malloc(sizeof(BPlusTree));tree->root = create_node(true); // 初始為葉子節點return tree;
}

B+ 樹節點內的二分查找

// 在節點中查找鍵的位置，或者找到合適往下走的通路
int btree_bin_search(BPlusTreeNode *node, int low, int high, int key) {//	二分查找法的時間復雜度是 O(log N)int mid;if (low > high || low < 0 || high < 0) {return -1;}while (low < high) {mid = (low + high) / 2;		//	向 0 取整嗎if (key > node->keys[mid]) {low = mid + 1;} else {high = mid - 1;}}return low;
}

B+ 樹的數據插入操作

insert_recursive 的遞歸實現思想不是 B 樹的 “防患于未然的未雨綢繆”，而是把 “底層的暗流涌動逐層的浮于水面之上”

葉子節點的數據插入是遞歸的邊界條件
只有葉子節點的插入所導致的節點分裂才有可能導致中間節點鍵的插入，因而需要逐層遞歸
回溯性地產生兄弟節點、以及需要提升的鍵
只要有一層說不用分裂節點，那之后的遞歸的回溯都會 trivival 化

bplus_tree_insert 函數是從 root 節點往下探索的，最終會包含對根節點的重塑


// 插入鍵到葉子節點
void insert_into_leaf(BPlusTreeNode* leaf, int key, void* value) {int idx =btree_bin_search(leaf, 0, leaf->key_count, key);// 如果鍵已存在，更新值if (idx < leaf->key_count && leaf->keys[idx] == key) {leaf->data_ptrs[idx] = value;return;}// 移動鍵和值以騰出空間for (int i = leaf->key_count; i > idx; i--) {leaf->keys[i] = leaf->keys[i - 1];leaf->data_ptrs[i] = leaf->data_ptrs[i - 1];}// 插入新鍵值leaf->keys[idx] = key;leaf->data_ptrs[idx] = value;leaf->key_count++;
}// 分裂葉子節點
BPlusTreeNode* split_leaf_node(BPlusTreeNode* leaf) {//  BPlusTreeNode* new_leaf = create_node(true);    //  true 代表生產葉子節點int split_index = leaf->key_count / 2;          //  中間指標是下一個葉子節點的鍵的開始指標// 移動后半部分鍵值到新葉子節點for (int i = split_index; i < leaf->key_count; i++) {new_leaf->keys[i - split_index] = leaf->keys[i];new_leaf->data_ptrs[i - split_index] = leaf->data_ptrs[i];leaf->keys[i] = INT_MAX; // 重置原位置}new_leaf->key_count = leaf->key_count - split_index;leaf->key_count = split_index;// 維護葉子節點鏈表new_leaf->next = leaf->next;leaf->next = new_leaf;return new_leaf;
}// 分裂內部節點，這是從終端由下往上傳來的壓力
BPlusTreeNode* split_internal_node(BPlusTreeNode* internal) {BPlusTreeNode* new_internal = create_node(false);int split_index = internal->key_count / 2;      //  分裂的位置int promote_key = internal->keys[split_index];  //  需要提升的鍵// 移動鍵和子節點指針，分裂出的右兄弟節點，不包含需要提升for (int i = split_index + 1; i < internal->key_count; i++) {new_internal->keys[i - split_index - 1] = internal->keys[i];new_internal->children[i - split_index - 1] = internal->children[i];internal->keys[i] = INT_MAX;}// 處理最后一個子節點指針new_internal->children[internal->key_count - split_index - 1] = internal->children[internal->key_count];new_internal->key_count = internal->key_count - split_index - 1;internal->key_count = split_index;return new_internal;
}// 插入操作的遞歸實現
void insert_recursive(BPlusTreeNode* node, int key, void* value,  BPlusTreeNode** new_child, int* promote_key) {//  node 和 new_child 是同級別的，node 分裂之后會產生右兄弟節點，去到更上一層后還會繼續被更新的//  如果是葉子節點if (node->is_leaf) {insert_into_leaf(node, key, value); //  葉子先插入數據// 檢查是否需要分裂，如果現在滿員了，我們可以未雨綢繆先行分裂if (node->key_count == M) {BPlusTreeNode* new_node = split_leaf_node(node);*new_child = new_node;*promote_key = new_node->keys[0]; // 提升新節點的第一個鍵，葉子節點允許與中間節點用同樣的鍵} else {*new_child = NULL;}return;     //  葉子節點是不會執行下面這些代碼的，是遞歸函數的邊界條件}// 內部節點 - 找到合適的子節點int idx =btree_bin_search(node, 0, node->key_count, key);//  找到分裂的位置BPlusTreeNode* child = node->children[idx];     BPlusTreeNode* new_child_node = NULL;int new_key = INT_MAX;insert_recursive(child, key, value, &new_child_node, &new_key); // 遞歸插入子節點，遞歸展開//------------------- 回溯 --------------------////  new_child_node 和 new_key 會被回溯定義，直至浮于水面，層層向上反映//  如果子節點分裂了，需要判斷當前更高一層的節點是否需要分裂if (new_child_node) {//  在內部節點中為新鍵騰出空間for (int i = node->key_count; i > idx; i--) {node->keys[i] = node->keys[i - 1];node->children[i + 1] = node->children[i];}// 插入新鍵和子節點指針node->keys[idx] = new_key;node->children[idx + 1] = new_child_node;node->key_count++;// 檢查是否需要分裂當前節點if (node->key_count == M) {BPlusTreeNode* new_node = split_internal_node(node);//  反射回草稿紙，記錄新產生的節點和需要提升的鍵*new_child = new_node;  *promote_key = node->keys[node->key_count]; // 提升新分裂節點的首鍵} else {*new_child = NULL;  //  本層節點不需要分裂}} else {*new_child = NULL;  //  子節點沒有分裂，那父節點更沒有分裂}
}// B+樹插入操作
void bplus_tree_insert(BPlusTree* tree, int key, void* value) {//  以下兩個變量取什么值并不重要，它們本身只是用來迭代求解的一張草稿紙BPlusTreeNode* new_child = NULL;    //  或許會分裂出的新節點int promote_key = INT_MAX;          //  或許有需要提升的鍵//  由于這兩個變量會經歷遞歸求解，最終有可能反射為，當前根節點的兄弟節點insert_recursive(tree->root, key, value, &new_child, &promote_key); //  遞歸展開//  底層插入數據的行為會一層一層地反映到根結點處//  root 和 new_child 是同級別的// 處理根節點分裂，產生一個新的根節點if (new_child) {BPlusTreeNode* new_root = create_node(false);   //  中間節點new_root->keys[0] = promote_key;new_root->children[0] = tree->root;new_root->children[1] = new_child;new_root->key_count = 1;tree->root = new_root;}
}

B+ 樹的刪除數據操作

delete_recursive 的遞歸實現思想依然是把 “底層的暗流涌動逐層的浮于水面之上”

只有葉子的刪除有可能導致節點合并，節點合并會導致中間節點的鍵刪除，這又有可能導致節點的再次合并。
葉子節點的數據刪除是遞歸的邊界條件
回溯性的判斷本層次是否需要節點合并、借兄弟節點數據，如果是后者或者都沒必要，此后的遞歸回溯都會 trivival 化


// 在葉子節點處刪除鍵值對數據
void delete_from_leaf(BPlusTreeNode* leaf, int key) {int idx =btree_bin_search(leaf, 0, leaf->key_count, key);if (idx < leaf->key_count && leaf->keys[idx] == key) {// 移動鍵和值以填充空隙for (int i = idx; i < leaf->key_count - 1; i++) {leaf->keys[i] = leaf->keys[i + 1];leaf->data_ptrs[i] = leaf->data_ptrs[i + 1];}leaf->keys[leaf->key_count - 1] = INT_MAX;leaf->key_count--;}
}// 從兄弟節點借鍵（葉子節點）
void borrow_from_sibling(BPlusTreeNode* node, BPlusTreeNode* sibling, BPlusTreeNode* parent, int parent_key_index, bool is_left_sibling) {//  sibling 指代兄弟節點if (is_left_sibling) {// 從左側兄弟借鍵，只能借最大鍵和其對應的數據（或者路標指針）int last_key = sibling->keys[sibling->key_count - 1];if (node->is_leaf) {//  葉子節點的兄弟借數據void* last_value = sibling->data_ptrs[sibling->key_count - 1];// 移動當前節點的鍵值，挪位置for (int i = node->key_count; i > 0; i--) {node->keys[i] = node->keys[i - 1];node->data_ptrs[i] = node->data_ptrs[i - 1];}         // 插入借來的鍵值node->keys[0] = last_key;node->data_ptrs[0] = last_value;node->key_count++;       } else {//  中間節點的兄弟借數據BPlusTreeNode* last_child = sibling->children[sibling->key_count];// 移動當前節點的鍵值，挪位置for (int i = node->key_count; i > 0; i--) {node->keys[i] = node->keys[i - 1];node->children[i] = node->data_ptrs[i - 1];}// 插入借來的鍵值node->keys[0] = last_key;node->children[0] = last_child;node->key_count++;}// 更新兄弟節點sibling->keys[sibling->key_count - 1] = INT_MAX;sibling->key_count--;// 更新父節點鍵parent->keys[parent_key_index-1] = node->keys[0];} else {// 從右側兄弟借鍵，只能借最小鍵和其對應的數據int first_key = sibling->keys[0];if (node->is_leaf) {//  葉子節點的兄弟借數據void* first_value = sibling->data_ptrs[0];// 插入借來的鍵值node->keys[node->key_count] = first_key;node->data_ptrs[node->key_count] = first_value;node->key_count++;// 更新兄弟節點for (int i = 0; i < sibling->key_count - 1; i++) {sibling->keys[i] = sibling->keys[i + 1];sibling->data_ptrs[i] = sibling->data_ptrs[i + 1];}} else {//  中間節點的兄弟借數據BPlusTreeNode* first_child = sibling->children[0];// 插入借來的鍵值node->keys[node->key_count] = first_key;node->children[node->key_count] = first_child;node->key_count++;// 更新兄弟節點for (int i = 0; i < sibling->key_count - 1; i++) {sibling->keys[i] = sibling->keys[i + 1];sibling->children[i] = sibling->children[i + 1];}}sibling->keys[sibling->key_count - 1] = INT_MAX;sibling->key_count--;// 更新父節點鍵node->keys[parent_key_index] = sibling->keys[0];}
}// 合并節點
void merge_nodes(BPlusTreeNode* left, BPlusTreeNode* right) {//  節點一旦合并，就意味著兄弟節點都沒有余糧可借了// 移動右側節點的鍵值到左側if (left->is_leaf) {for (int i = 0; i < right->key_count; i++) {left->keys[left->key_count + i] = right->keys[i];left->data_ptrs[left->key_count + i] = right->data_ptrs[i];}left->key_count += right->key_count;left->next = right->next;// 釋放右側節點free(right);} else {for (int i = 0; i < right->key_count; i++) {left->keys[left->key_count + i] = right->keys[i];left->children[left->key_count + i] = right->data_ptrs[i];}left->children[left->key_count + right->key_count] = right->children[right->key_count];left->key_count += right->key_count;// 釋放右側節點free(right);}}// 刪除操作的遞歸實現
bool delete_recursive(BPlusTreeNode* node, int key, int* min_key) {//  min_key 指代 node 更新后的最小鍵值，它會被遞歸更新的，直至浮出水面//  返回值 bool 表示操作是否需要進一步回溯修改。在葉子節點層次，刪除 node 的一個數據后，數據的容量是否低于最小限度。 在中間節點層次，適應底層修改后，數據的容量是否低于最小限度。//  節點合并有可能會導致問題上傳，借節點則不會導致問題上傳// 葉子節點處理if (node->is_leaf) {//  這是遞歸的邊界條件int idx =btree_bin_search(node, 0, node->key_count, key);if (idx < node->key_count && node->keys[idx] == key) {delete_from_leaf(node, key);*min_key = (node->key_count > 0) ? node->keys[0] : INT_MAX;return node->key_count < MIN_KEYS;  //  節點數據量嚴重缺乏}return false; // 鍵不存在}// 內部節點 - 找到合適的子節點int idx = btree_bin_search(node, 0, node->key_count, key);    //  idx 相位所對應的路由指針上所有的鍵都小于本節點第 idx 位的鍵BPlusTreeNode* child = node->children[idx]; //  找到路牌往下走int new_min_key;bool child_underflow = delete_recursive(child, key, &new_min_key);  //  展開遞歸，遞歸的最內層就是葉子節點//-------------------------- 回溯 ----------------------------//// 子節點已完成更新鍵值，現在父節點對應的路牌也要更新成對應子節點的最小keyif (idx > 0 && new_min_key != INT_MAX && new_min_key != node->keys[idx - 1]) {node->keys[idx - 1] = new_min_key;}// 處理子節點下溢if (child_underflow) {BPlusTreeNode* left_sibling = (idx > 0) ? node->children[idx - 1] : NULL;BPlusTreeNode* right_sibling = (idx < node->key_count) ? node->children[idx + 1] : NULL;// 嘗試從左兄弟借鍵if (left_sibling && left_sibling->key_count > MIN_KEYS) {//  借數據并不會導致上層結構的變化borrow_from_sibling(child, left_sibling, node, idx, true);return false;} // 嘗試從右兄弟借鍵else if (right_sibling && right_sibling->key_count > MIN_KEYS) {//  借數據并不會導致上層結構的變化borrow_from_sibling(child, right_sibling, node, idx, false);return false;}// 合并節點else {if (left_sibling) {// 與左兄弟合并if (child->is_leaf) {merge_nodes(left_sibling, child);}// 更新父節點for (int i = idx; i < node->key_count; i++) {node->keys[i - 1] = node->keys[i];node->children[i] = node->children[i + 1];}node->keys[node->key_count - 1] = INT_MAX;node->key_count--;} else if (right_sibling) {// 與右兄弟合并if (child->is_leaf) {merge_nodes(child, right_sibling);}// 更新父節點for (int i = idx + 1; i < node->key_count; i++) {node->keys[i - 1] = node->keys[i];node->children[i] = node->children[i + 1];}node->keys[node->key_count - 1] = INT_MAX;node->key_count--;}return node->key_count < MIN_KEYS;}}return false;
}// B+樹刪除操作
void bplus_tree_delete(BPlusTree* tree, int key) {int min_key;bool root_underflow = delete_recursive(tree->root, key, &min_key);  //  讓所有問題浮出水面// 處理根節點下溢if (root_underflow && !tree->root->is_leaf && tree->root->key_count == 0) {BPlusTreeNode* old_root = tree->root;tree->root = tree->root->children[0];free(old_root);}
}

范圍查詢與全局遍歷

B+ 樹的范圍查詢要遠比 B 樹的好寫，因為 B+ 樹的葉子節點是可以指向下一個相鄰的葉子節點。

// 查找鍵對應的值
void* bplus_tree_search(BPlusTree* tree, int key) {BPlusTreeNode* node = tree->root;while (!node->is_leaf) {int idx =btree_bin_search(node, 0, node->key_count, key);node = node->children[idx];}int idx =btree_bin_search(node, 0, node->key_count, key);if (idx < node->key_count && node->keys[idx] == key) {return node->data_ptrs[idx];}return NULL; // 未找到
}// 范圍查詢
void bplus_tree_range_query(BPlusTree* tree, int start, int end) {BPlusTreeNode* node = tree->root;// 找到起始鍵所在的葉子節點while (!node->is_leaf) {int idx =btree_bin_search(node, 0, node->key_count, start);node = node->children[idx];}// 在葉子節點鏈表中遍歷while (node != NULL) {for (int i = 0; i < node->key_count; i++) {// 鍵在范圍內if (node->keys[i] >= start && node->keys[i] <= end) {printf("Key: %d, Value: %d\n", node->keys[i], *(int*)(node->data_ptrs[i]));  //  %p 是指針占位符}// 超過范圍，停止查詢if (node->keys[i] > end) {return;}}node = node->next;}
}

我們亦可按照樹的層次去打印 B+ 樹的結構

// 打印B+樹（輔助函數）
void print_bplus_tree(BPlusTreeNode* node, int level) {if (node == NULL) return;printf("Level %d: ", level);for (int i = 0; i < node->key_count; i++) {printf("%d ", node->keys[i]);}printf("\n");if (!node->is_leaf) {for (int i = 0; i <= node->key_count; i++) {print_bplus_tree(node->children[i], level + 1);}}
}

銷毀 B+ 樹

// 釋放B+樹內存
void free_bplus_tree(BPlusTreeNode* node) {if (node == NULL) return;if (!node->is_leaf) {for (int i = 0; i <= node->key_count; i++) {free_bplus_tree(node->children[i]);}}free(node);
}

測試代碼（主函數）

測試量為 200 個插入。

// 測試用例
int main() {BPlusTree* tree = init_bplus_tree();// 插入測試printf("Inserting keys...\n");for (int i = 1; i <= 200; i++) {int* value = (int*)malloc(sizeof(int));*value = i * 100;bplus_tree_insert(tree, i, value);}printf("B+ Tree structure:\n");print_bplus_tree(tree->root, 0);// 搜索測試printf("\nSearching keys:\n");for (int i = 5; i <= 15; i += 3) {void* result = bplus_tree_search(tree, i);if (result) {printf("Key %d found. Value: %d\n", i, *((int*)result));} else {printf("Key %d not found.\n", i);}}// 范圍查詢測試printf("\nRange query [7, 15]:\n");bplus_tree_range_query(tree, 7, 15);// 刪除測試printf("\nDeleting keys 8, 12, 15...\n");bplus_tree_delete(tree, 8);bplus_tree_delete(tree, 12);bplus_tree_delete(tree, 15);printf("\nB+ Tree structure after deletion:\n");print_bplus_tree(tree->root, 0);// 再次范圍查詢printf("\nRange query [7, 15] after deletion:\n");bplus_tree_range_query(tree, 7, 15);// 清理free_bplus_tree(tree->root);free(tree);return 0;
}

運行效果還 OK。

qiming@qiming:~/share/CTASK/data-structure$ gcc -o bp bptree_test.c
qiming@qiming:~/share/CTASK/data-structure$ ./bp
Inserting keys...
B+ Tree structure:
Level 0: 55 109 163 
Level 1: 19 37 
Level 2: 7 13 
Level 3: 3 5 
Level 4: 1 2 
Level 4: 3 4 
Level 4: 5 6 
Level 3: 9 11 
Level 4: 7 8 
Level 4: 9 10 
Level 4: 11 12 
Level 3: 15 17 
Level 4: 13 14 
Level 4: 15 16 
Level 4: 17 18 
Level 2: 25 31 
Level 3: 21 23 
Level 4: 19 20 
Level 4: 21 22 
Level 4: 23 24 
Level 3: 27 29 
Level 4: 25 26 
Level 4: 27 28 
Level 4: 29 30 
Level 3: 33 35 
Level 4: 31 32 
Level 4: 33 34 
Level 4: 35 36 
Level 2: 43 49 
Level 3: 39 41 
Level 4: 37 38 
Level 4: 39 40 
Level 4: 41 42 
Level 3: 45 47 
Level 4: 43 44 
Level 4: 45 46 
Level 4: 47 48 
Level 3: 51 53 
Level 4: 49 50 
Level 4: 51 52 
Level 4: 53 54 
Level 1: 73 91 
Level 2: 61 67 
Level 3: 57 59 
Level 4: 55 56 
Level 4: 57 58 
Level 4: 59 60 
Level 3: 63 65 
Level 4: 61 62 
Level 4: 63 64 
Level 4: 65 66 
Level 3: 69 71 
Level 4: 67 68 
Level 4: 69 70 
Level 4: 71 72 
Level 2: 79 85 
Level 3: 75 77 
Level 4: 73 74 
Level 4: 75 76 
Level 4: 77 78 
Level 3: 81 83 
Level 4: 79 80 
Level 4: 81 82 
Level 4: 83 84 
Level 3: 87 89 
Level 4: 85 86 
Level 4: 87 88 
Level 4: 89 90 
Level 2: 97 103 
Level 3: 93 95 
Level 4: 91 92 
Level 4: 93 94 
Level 4: 95 96 
Level 3: 99 101 
Level 4: 97 98 
Level 4: 99 100 
Level 4: 101 102 
Level 3: 105 107 
Level 4: 103 104 
Level 4: 105 106 
Level 4: 107 108 
Level 1: 127 145 
Level 2: 115 121 
Level 3: 111 113 
Level 4: 109 110 
Level 4: 111 112 
Level 4: 113 114 
Level 3: 117 119 
Level 4: 115 116 
Level 4: 117 118 
Level 4: 119 120 
Level 3: 123 125 
Level 4: 121 122 
Level 4: 123 124 
Level 4: 125 126 
Level 2: 133 139 
Level 3: 129 131 
Level 4: 127 128 
Level 4: 129 130 
Level 4: 131 132 
Level 3: 135 137 
Level 4: 133 134 
Level 4: 135 136 
Level 4: 137 138 
Level 3: 141 143 
Level 4: 139 140 
Level 4: 141 142 
Level 4: 143 144 
Level 2: 151 157 
Level 3: 147 149 
Level 4: 145 146 
Level 4: 147 148 
Level 4: 149 150 
Level 3: 153 155 
Level 4: 151 152 
Level 4: 153 154 
Level 4: 155 156 
Level 3: 159 161 
Level 4: 157 158 
Level 4: 159 160 
Level 4: 161 162 
Level 1: 181 
Level 2: 169 175 
Level 3: 165 167 
Level 4: 163 164 
Level 4: 165 166 
Level 4: 167 168 
Level 3: 171 173 
Level 4: 169 170 
Level 4: 171 172 
Level 4: 173 174 
Level 3: 177 179 
Level 4: 175 176 
Level 4: 177 178 
Level 4: 179 180 
Level 2: 187 193 
Level 3: 183 185 
Level 4: 181 182 
Level 4: 183 184 
Level 4: 185 186 
Level 3: 189 191 
Level 4: 187 188 
Level 4: 189 190 
Level 4: 191 192 
Level 3: 195 197 199 
Level 4: 193 194 
Level 4: 195 196 
Level 4: 197 198 
Level 4: 199 200 Searching keys:
Key 5 not found.
Key 8 not found.
Key 11 not found.
Key 14 not found.Range query [7, 15]:
Key: 7, Value: 700
Key: 8, Value: 800
Key: 9, Value: 900
Key: 10, Value: 1000
Key: 11, Value: 1100
Key: 12, Value: 1200
Key: 13, Value: 1300
Key: 14, Value: 1400
Key: 15, Value: 1500Deleting keys 8, 12, 15...B+ Tree structure after deletion:
Level 0: 55 109 163 
Level 1: 19 37 
Level 2: 7 21997 
Level 3: 3 32545 
Level 4: 1 2 
Level 4: 3 4 
Level 4: 5 6 
Level 3: 9 11 
Level 4: 7 8 
Level 4: 9 10 
Level 4: 11 12 
Level 3: 15 17 
Level 4: 13 14 
Level 4: 15 16 
Level 4: 17 18 
Level 2: 25 31 
Level 3: 21 23 
Level 4: 19 20 
Level 4: 21 22 
Level 4: 23 24 
Level 3: 27 29 
Level 4: 25 26 
Level 4: 27 28 
Level 4: 29 30 
Level 3: 33 35 
Level 4: 31 32 
Level 4: 33 34 
Level 4: 35 36 
Level 2: 43 49 
Level 3: 39 41 
Level 4: 37 38 
Level 4: 39 40 
Level 4: 41 42 
Level 3: 45 47 
Level 4: 43 44 
Level 4: 45 46 
Level 4: 47 48 
Level 3: 51 53 
Level 4: 49 50 
Level 4: 51 52 
Level 4: 53 54 
Level 1: 73 91 
Level 2: 61 67 
Level 3: 57 59 
Level 4: 55 56 
Level 4: 57 58 
Level 4: 59 60 
Level 3: 63 65 
Level 4: 61 62 
Level 4: 63 64 
Level 4: 65 66 
Level 3: 69 71 
Level 4: 67 68 
Level 4: 69 70 
Level 4: 71 72 
Level 2: 79 85 
Level 3: 75 77 
Level 4: 73 74 
Level 4: 75 76 
Level 4: 77 78 
Level 3: 81 83 
Level 4: 79 80 
Level 4: 81 82 
Level 4: 83 84 
Level 3: 87 89 
Level 4: 85 86 
Level 4: 87 88 
Level 4: 89 90 
Level 2: 97 103 
Level 3: 93 95 
Level 4: 91 92 
Level 4: 93 94 
Level 4: 95 96 
Level 3: 99 101 
Level 4: 97 98 
Level 4: 99 100 
Level 4: 101 102 
Level 3: 105 107 
Level 4: 103 104 
Level 4: 105 106 
Level 4: 107 108 
Level 1: 127 145 
Level 2: 115 121 
Level 3: 111 113 
Level 4: 109 110 
Level 4: 111 112 
Level 4: 113 114 
Level 3: 117 119 
Level 4: 115 116 
Level 4: 117 118 
Level 4: 119 120 
Level 3: 123 125 
Level 4: 121 122 
Level 4: 123 124 
Level 4: 125 126 
Level 2: 133 139 
Level 3: 129 131 
Level 4: 127 128 
Level 4: 129 130 
Level 4: 131 132 
Level 3: 135 137 
Level 4: 133 134 
Level 4: 135 136 
Level 4: 137 138 
Level 3: 141 143 
Level 4: 139 140 
Level 4: 141 142 
Level 4: 143 144 
Level 2: 151 157 
Level 3: 147 149 
Level 4: 145 146 
Level 4: 147 148 
Level 4: 149 150 
Level 3: 153 155 
Level 4: 151 152 
Level 4: 153 154 
Level 4: 155 156 
Level 3: 159 161 
Level 4: 157 158 
Level 4: 159 160 
Level 4: 161 162 
Level 1: 181 
Level 2: 169 175 
Level 3: 165 167 
Level 4: 163 164 
Level 4: 165 166 
Level 4: 167 168 
Level 3: 171 173 
Level 4: 169 170 
Level 4: 171 172 
Level 4: 173 174 
Level 3: 177 179 
Level 4: 175 176 
Level 4: 177 178 
Level 4: 179 180 
Level 2: 187 193 
Level 3: 183 185 
Level 4: 181 182 
Level 4: 183 184 
Level 4: 185 186 
Level 3: 189 191 
Level 4: 187 188 
Level 4: 189 190 
Level 4: 191 192 
Level 3: 195 197 199 
Level 4: 193 194 
Level 4: 195 196 
Level 4: 197 198 
Level 4: 199 200 Range query [7, 15] after deletion:
Key: 7, Value: 700
Key: 8, Value: 800
Key: 9, Value: 900
Key: 10, Value: 1000
Key: 11, Value: 1100
Key: 12, Value: 1200
Key: 13, Value: 1300
Key: 14, Value: 1400
Key: 15, Value: 1500
qiming@qiming:~/share/CTASK/data-structure$