B+ 樹是一個多叉樹排序樹，其每個節(jié)點中可能包含多個 key。主要是用來對 OLTB 的數(shù)據(jù)庫來進行索引。對于 insert, delete 操作需要調(diào)整樹的結(jié)構(gòu)保證這棵樹的平衡性，使其所有的葉子節(jié)點的深度都是一樣的。與此同時需要讓每個節(jié)點有一定數(shù)量的 key 不能過多，也不能過少。 (todo 補充B+樹的意義)。
1 B+ 樹的性質(zhì)
- insert delete 操作需要保證這棵樹的平衡性。
- 除根節(jié)點外的每個節(jié)點至少保證 50% 空間被 key 占用。
- 對于查詢操作，只需要訪問樹的高度個節(jié)點。
- 假設(shè)每個節(jié)點有 m 個 key， 對于非根節(jié)點
, 其中
是 B+ 樹的參數(shù)，叫做樹的 order 用來定義節(jié)點的容量。對于根節(jié)點
.
2 B+ 節(jié)點的 format
B+ 樹有兩種節(jié)點，中間節(jié)點和葉子節(jié)點，共同點是他們都包含了 key，不同點是，中間節(jié)點包含了指向子樹的指針。**葉子節(jié)點沒有指向子樹的指針, 但是包含了 key 所對應(yīng)的 record 或者是指向 record 的指針。并且葉子節(jié)點有指向其 相鄰的葉子節(jié)點的指針(用來遍歷 B+ 樹)。
非葉子節(jié)點有 個 key 和
個指針
指向子節(jié)點。所有的 key 都是以什序排列
, 其中
指針指向的子樹的所有的 key 都小于
,
不存在。其他指針
指向的子樹的 key 的值大于等于
。下圖就是一個
B+ 樹的例子。
當然葉子節(jié)點也可以作為根節(jié)點，下圖就是只插入三個 key 時 B+ tree 的樣子。
注意:本文中的后續(xù)舉例說明的 B+ 樹的 d 默認為 2。
3 插入操作
B+ 樹插入的 entry 一般包含了一個 key 與一個 val。
首先找到應(yīng)該插入的葉子節(jié)點，并將 <key,val> 插入。
如果插入后的葉子節(jié)點的 ，需要將將節(jié)點分裂(split)為 d 與 d+1 兩個節(jié)點，并且將右邊節(jié)點的 lowKey（最小的key）插入到父親節(jié)點。
split 需要分三種情況討論:
1）被 split 的節(jié)點沒有父親節(jié)點，即根節(jié)點為葉子節(jié)點。需要創(chuàng)建一個 中間節(jié)點作為根節(jié)點，并且將 split 的 pivot 插入到這個新的根節(jié)點，其兩個指針分別指向 split 出來的兩個新的葉子節(jié)點。
如下圖，是一個 d=2 的 B+ 樹，繼續(xù)插入一個<8:4> 的pair:
樹將變?yōu)橄旅娴臉幼?
- 如果有父親節(jié)點且父親節(jié)點沒有滿，被split 出來新的節(jié)點 pointer 和 split 的 pivot 插入父親節(jié)點。如下圖向上圖中的 B+ 樹中連續(xù)插入 <10,5>和 <12,6> 兩個 entry將得到下圖的結(jié)果。
3）如果父親節(jié)點已經(jīng)插滿，父親節(jié)點也需要分裂遞歸向上插入 split 出來的 node 與 pivot
如果向上圖插入<17,4> 這個 entry 會導(dǎo)致節(jié)點分裂，并且 pivot 為 key = 15。此時其父節(jié)點中上插入 key=15, 以及 pointer 指向被分裂出來的 node 。而在父親節(jié)點插入的新 <key,pointer> 會導(dǎo)致父親節(jié)點進行分裂，并且同樣在 key = 15 處分裂。此時由于父親節(jié)點沒有父親節(jié)點了，創(chuàng)建一個新的 root 節(jié)點。如下圖：
?? 這里需要注意:
split 中間節(jié)點操作與 split 葉子節(jié)點有少許的不同，葉子節(jié)點會將 pivot 插入父親節(jié)點，并且保留這個 pivot。而對于中間節(jié)點來說，這個pivot 在插入父親節(jié)點后，在當前節(jié)點中會被移除掉。
4 刪除操作
當刪除某一個 key 后，可能會導(dǎo)致葉子節(jié)點 需要改變樹的結(jié)構(gòu)以滿足 B+ 樹的定義。這里涉及到兩種可能的操作，使得 B+ 樹滿足定義。他們?yōu)? 重排(redistribute) 和 合并 (merge) 。
刪除key的操作是通過遞歸實現(xiàn)。對從根節(jié)點到key所在的葉子節(jié)點遞歸調(diào)用刪除操作。如果子樹的刪除操作不會導(dǎo)致點該節(jié)點中 key 的數(shù)量過小即 就直接返回。反之需要對該節(jié)點進行 redistribute 或者 merge。
首先嘗試 redistribute 即分別向左右 sibling (同一個parent 下面的節(jié)點) 一個 key 讓當前節(jié)點滿足 B+樹的要求?？梢?lend 的 sibling 需滿足 。如果找不到這樣的 sibling 則說明要么沒有 sibling 要么 sibling (
) 。則此時可以嘗試 merge。
下面將刪除操作分別在葉子節(jié)點和中間節(jié)點中運用進行討論，即刪除后節(jié)點的 。
4.1 葉子節(jié)點
4.1.1 redistribute
4.1.1.1 向左兄弟借一個key
如果當前節(jié)點不是其父親節(jié)點的最左的兒子，并且其左邊的兄弟的 key 的數(shù)量 ，向其左兄弟借一個 key(左兄弟的最大的key)， 更新當前節(jié)點的父親節(jié)點指向當前節(jié)點所對應(yīng)的key。例如對上圖的B+樹中刪除 <20,4> 這個值，其所在的節(jié)點會向其左兄弟借 <17,4>這個 entry 并將父親節(jié)點中的 key 從 20 改為 17。
4.1.1.2 向右兄弟借一個 key
如果當前節(jié)點不是其父親節(jié)點的最右邊的兒子，并且其右邊的兄弟的 key 的數(shù)量 ，向其右兄弟借一個 key(左兄弟的最小的key)，更新父親節(jié)點指向右兄弟的 pionter 所對應(yīng)的 key。例如如果刪除上圖中的 <21,4> 這個 key，這個節(jié)點將會向右兄弟借 <22,4> 這個key 父親節(jié)點中的 22 將更新為 25.結(jié)果如下圖所示:
4.1.2 merge
4.1.2.1 merge 到左兄弟
如果當前節(jié)點有左兄弟，并且左兄弟的 key 的數(shù)量 ，將當前節(jié)點上的key copy 到左兄弟，刪除當前節(jié)點，并且在父親節(jié)點將當前節(jié)點的 pointer 以及 key 刪掉。
例如將上圖中 刪除 21， 所在的節(jié)將 merge 其左兄弟，父親節(jié)點的keys 將刪除 18 以及 當前node 的 pointer，最后parent只剩下 23,25，如下圖。
4.1.2.2 merge 右兄弟
如果不能merge到左兄弟(當前節(jié)點為 parent 最左邊的兒子) merge 其右兄弟。 在父親節(jié)點中將右兄弟的 pointer 以及key刪除掉。如果將 4.1.1.3 中的第一張圖的 <16,4> 刪除，將會導(dǎo)致其節(jié)點 merge 右邊的兄弟，其父親節(jié)點將變?yōu)?[23,25].
4.2 中間節(jié)點
上面的部分只討論了葉子節(jié)點出現(xiàn) redistribute 和 merge的情況。在某些情況下這些操作將會導(dǎo)致中間節(jié)點的 key的數(shù)量不滿足 B+ 樹的要求。此時需要將中間節(jié)點進行 redistribute 或者merge。例如上圖中如果刪除 25 將會導(dǎo)致葉子節(jié)點的merge，其父親節(jié)點將會只有一個 key。這將不能滿足B+樹的限制。
4.2.1 redistribute
4.2.1.1 向左兄弟借一個 key
由于中間節(jié)點的每一個 entry 是 <key,pointer> 的組合，如果直接將左兄弟的最大的key以及它所代表pointer copy 過來會導(dǎo)致當前節(jié)點少了一個 key， 此時需要將父親節(jié)點所對應(yīng)的 key copy 到中間。并且更新父親節(jié)點中，指向當前節(jié)點的 pointer 所對應(yīng)的 key為借過來的 key。例如，將上圖中的 17 刪除掉，將會導(dǎo)致 [20,22]這個節(jié)點的變?yōu)?[22], 需要向左邊的兄弟借一個 10 的key過來，并且將父親節(jié)點的 15 copy 下來，最終變?yōu)?[10,15,22]，并更新父親節(jié)點的 key。如下圖所示:
4.2.1.2 向右邊兄弟借一個 key
同理，需要將右兄弟的在父親節(jié)點中pointer 說對應(yīng)的 key copy 下來，并且更新父親節(jié)點的 key。稍微有點區(qū)別的是，右邊兄弟的第一個兒子的指針是不包含 key 的，所以當前節(jié)點只需要將指針直接拿過來，并刪除掉 right silbing 最小的那個key。
如圖，如果將圖中的 10 刪除，會導(dǎo)致 [5，10] 這個節(jié)點變?yōu)?[5] 并向右邊的兄弟借一個pointer，并且父親節(jié)點中key被更為 17。
4.2.2 merge
merge 的操作和 redistribute 的操作類似，redistribute 是只borrow 一個 key， 而merge 是將所有的 key 都 borrow 過來。稍有一點區(qū)別就是 borrow 是 update 父親節(jié)點中的 key, 而 merge 是直接刪除，可以看作是 split 的逆過程。
4.2.2.1 merge to left
如上圖如果刪除 18 [24,30] 這個節(jié)點將變?yōu)?[30], 會把當前節(jié)點 merge 到左邊的 [6,12] 這個節(jié)點, 最后變成 [6,12,18,30] 這個節(jié)點，如下圖所示。
4.2.2.1 merge right
如果刪除 15 會將右邊的節(jié)點 merge 過來 當前節(jié)點變?yōu)閇6,18,24,30]，如下圖所示。
4.2.2.2 root 變?yōu)?空
如何遞歸刪除到根節(jié)點時()，并且兩個子節(jié)點發(fā)生 merge，這樣會導(dǎo)致根節(jié)點的key 的數(shù)量為零，此時就需要刪除根節(jié)點。
例如刪除下圖中的 9 這個key 會讓兩個子節(jié)點 merge。
刪除后的B+樹如下圖:
