正確理解 B+樹(shù)
B+樹(shù)是為磁盤和存儲(chǔ)工具設(shè)計(jì)的一種數(shù)據(jù)結(jié)構(gòu)，它是一種平衡查找樹(shù)，它在查找，插入、修改方面的時(shí)間復(fù)雜度都穩(wěn)定為 O(logn)
節(jié)點(diǎn)
B+樹(shù)節(jié)點(diǎn)是一組按照key有序的元素，B+樹(shù)包含兩種類型的節(jié)點(diǎn)，一種是索引節(jié)點(diǎn)，一種是葉子節(jié)點(diǎn)
索引節(jié)點(diǎn)也叫內(nèi)部節(jié)點(diǎn)，索引節(jié)點(diǎn)只包含key，不包含data, 節(jié)點(diǎn)的 key是升序排列的，對(duì)于指定的索引節(jié)點(diǎn)key來(lái)說(shuō)，它左子樹(shù)上所有的key都小于它的key，它右子樹(shù)上所有的key都大于等于它的key
葉節(jié)點(diǎn)上存儲(chǔ)的是主鍵和數(shù)據(jù)(key和data), 所有的葉節(jié)點(diǎn)都在同一高度上，節(jié)點(diǎn)按key 從小到大并且通過(guò)指針使得彼此鏈接，這樣，所有的葉節(jié)點(diǎn)組成了一個(gè)雙向有序鏈表，葉節(jié)點(diǎn)這樣做的好處是在不訪問(wèn)索引的情況下能順序檢索數(shù)據(jù)，也能很好的支持范圍查詢的快處理
B+樹(shù)特點(diǎn)
階數(shù)為 m 的B+樹(shù)，每個(gè)索引節(jié)點(diǎn)最多有 m 個(gè)子節(jié)點(diǎn)，每個(gè)索引節(jié)點(diǎn)頁(yè)面最多存儲(chǔ) m - 1 個(gè)索引key
所有索引節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)在 Math.ceil(m / 2) 和 m 之間
B +樹(shù)之所以稱為平衡樹(shù)，是因?yàn)閺母?jié)點(diǎn)到葉節(jié)點(diǎn)的每條路徑都具有相同的長(zhǎng)度。平衡樹(shù)意味著所有對(duì)單個(gè)值的搜索都需要從磁盤讀取相同數(shù)量的頁(yè)面。
填充因子
B+樹(shù)使用填充因子來(lái)控制頁(yè)面的分裂和合并，設(shè)置數(shù)據(jù)占用頁(yè)面空間的百分比，目的是為后面的數(shù)據(jù)預(yù)留一部分頁(yè)空間，當(dāng)有新數(shù)據(jù)時(shí)，可以放到預(yù)留的頁(yè)空間中，避免分頁(yè)的發(fā)生
默認(rèn)的填充因子是50%，對(duì)于一棵m階的B+樹(shù)，填充因子是 m/2
B+樹(shù)操作
B+樹(shù)常用操作涉及到查詢、插入、刪除、范圍查詢, 為了便于說(shuō)明，下面所有操作的例子中的B+樹(shù)無(wú)特殊說(shuō)明都是5階樹(shù)
每個(gè)頁(yè)面最多有4個(gè)key，大于等于5個(gè)時(shí)就需要分裂或者旋轉(zhuǎn)合并
填充因子默認(rèn)是50%，頁(yè)面中已經(jīng)使用了的數(shù)量為2表示填充因子為50%，同理，小于2時(shí)候表示填充因子小于50%，大于2時(shí)候表示填充因子大于50%
查詢
B+樹(shù)的索引節(jié)點(diǎn)是有序的，查詢單個(gè)key的話直接用二分查找定位到目標(biāo)葉子頁(yè)面，在目標(biāo)葉子頁(yè)面中順序遍歷，找到目標(biāo)key，則返回葉子頁(yè)面中目標(biāo)key對(duì)應(yīng)的數(shù)據(jù)
插入
B+樹(shù)的插入操作完成以后，有以下幾種情況
1. 葉節(jié)點(diǎn)和索引節(jié)點(diǎn)沒(méi)有滿
這種情況插入操作步驟最少，根據(jù)key把數(shù)據(jù)插入到葉節(jié)點(diǎn)已經(jīng)排序的位置上即可，下圖中是插入key為 23的數(shù)據(jù)，23會(huì)插入到包含 15, 21 的葉子頁(yè)面中，插入之后葉子頁(yè)面沒(méi)有滿，不用處理頁(yè)面分裂的情況
2. 葉節(jié)點(diǎn)滿了，索引節(jié)點(diǎn)未滿
步驟：
(1)：葉子頁(yè)面分裂成兩個(gè)頁(yè)面
(2): 把中間行數(shù)據(jù)的key按順序加入到上一層的索引頁(yè)中
(3): 所有小于中間行數(shù)據(jù)key的數(shù)據(jù)放到左葉子頁(yè)面
(4): 所有大于等于中間行數(shù)據(jù)key的數(shù)據(jù)放到右葉子葉面
往圖(2) 的B+樹(shù)中插入key為28的數(shù)據(jù)，這條數(shù)據(jù)會(huì)插入到包含15，21，23，27的葉子頁(yè)面中，插入之后，該頁(yè)面數(shù)據(jù)已滿，必須要分裂成如下所示的兩個(gè)頁(yè)面：
| 左葉子頁(yè)面 | 右葉子頁(yè)面 |
|---|---|
| 15，21 | 23，27，28 |
中間行數(shù)據(jù)key為：23，放到上一層的索引頁(yè)面中15的后面，下面圖(3)是插入key為28的結(jié)果
3. 葉子頁(yè)面和索引頁(yè)面都滿了
步驟：
(1)：葉節(jié)點(diǎn)頁(yè)面分裂成左右兩個(gè)葉子頁(yè)面
(2): 把中間行數(shù)據(jù)的key按順序加入到索引頁(yè)中
(3): 所有小于中間行數(shù)據(jù)key的數(shù)據(jù)放到左葉子頁(yè)面
(4): 所有大于等于中間行數(shù)據(jù)key的數(shù)據(jù)放到右葉子頁(yè)面
(5): 上面步驟(2)執(zhí)行之后,索引頁(yè)面滿了，分裂成左右兩個(gè)索引頁(yè)
(6): 所有小于索引頁(yè)中間的key的放到左邊索引頁(yè)
(7): 所有大于索引頁(yè)中間的key的放到右邊索引頁(yè)
(8): 把索引頁(yè)中間的key放到更高一層的索引頁(yè)
如果步驟(8)執(zhí)行之后，更高一層的索引頁(yè)滿了，繼續(xù)執(zhí)行(5)-(8)步驟
圖(4) 的B+樹(shù)插入key為30的數(shù)據(jù)，這條數(shù)據(jù)會(huì)插入到 23, 27, 28, 29 的葉子頁(yè)面中，插入之后，該頁(yè)面數(shù)據(jù)已滿，必須要分裂成如下所示的兩個(gè)頁(yè)面：
| 左葉子頁(yè)面 | 右葉子頁(yè)面 |
|---|---|
| 23，27 | 28，29，30 |
中間行數(shù)據(jù)key為：28，放到索引頁(yè)面中23 的后面
28 放到索引頁(yè)面23的后面之后，索引頁(yè)變成了4, 7, 15, 23, 28, 這時(shí)索引頁(yè)也滿了，分裂成如下所示的三個(gè)頁(yè)面 :
| 左索引頁(yè) | 右索引頁(yè) | 更高一層索引頁(yè) |
|---|---|---|
| 4，7 | 23，28 | 15 |
下面圖(5)為插入key為30數(shù)據(jù)之后，葉子頁(yè)面和索引頁(yè)面分裂之后的結(jié)果：
旋轉(zhuǎn)
B+樹(shù)的插入操作會(huì)有頁(yè)面分裂的情況，頁(yè)面分裂就會(huì)有產(chǎn)生磁盤IO，相對(duì)內(nèi)存，磁盤 IO 要慢得多，所以為了減少磁盤IO操作，就要盡可能的減少頁(yè)面分裂，充分利用頁(yè)面空間，因此B+樹(shù)提供了旋轉(zhuǎn)操作
旋轉(zhuǎn)操作的應(yīng)用場(chǎng)景: B+樹(shù)葉子頁(yè)面空間已經(jīng)滿了，但是它的左右兄弟頁(yè)面沒(méi)有滿
葉子頁(yè)面空間滿了，B+樹(shù)會(huì)優(yōu)先檢查左右兄弟葉子頁(yè)面是否能容納數(shù)據(jù)，當(dāng)左右兄弟頁(yè)面空間都滿了時(shí)，才會(huì)考慮頁(yè)面分裂
圖(6)中，插入key為12的數(shù)據(jù)，葉子頁(yè)面空間滿了，這時(shí)B+樹(shù)先檢查左兄弟頁(yè)面是否有多余的空間，通過(guò)旋轉(zhuǎn)，把key分別為 7, 10, 11, 12, 13的葉子中的 7 移動(dòng)到左兄弟頁(yè)面中,移動(dòng)完成之后，左兄弟的key變成了 2, 5, 7
同時(shí)，葉子中key為7的數(shù)據(jù)在上層索引頁(yè)中也有記錄，所以需要把上層索引頁(yè)中key為7修改為 10，修改之后上層索引key分別為 10, 15，最終的結(jié)果如下圖(7)所示
葉子頁(yè)面插入新數(shù)據(jù)之后，頁(yè)面空間已滿，原本頁(yè)面是需要分裂的，但是通過(guò)把當(dāng)前頁(yè)面上的數(shù)據(jù)移動(dòng)到能容納數(shù)據(jù)的兄弟頁(yè)面中，減少了一次頁(yè)分裂，也即減少了一次磁盤IO操作
刪除
B+樹(shù)的刪除操作完成以后，有以下幾種情況
1. 葉子頁(yè)面和索引頁(yè)面填充因子都大于等于50%
這種情況直接刪除節(jié)點(diǎn)，頁(yè)面會(huì)把刪除節(jié)點(diǎn)的位置標(biāo)記為空，以便存放后續(xù)其他的數(shù)據(jù),同時(shí)，如果刪除的key出現(xiàn)在上層的索引頁(yè)面中，需要用葉子頁(yè)面中被刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)key去替換它
圖(8)中 7是待刪除的節(jié)點(diǎn)，刪除7后，葉子頁(yè)面填充因子剛好等于50%，因?yàn)楸粍h除的7在上層的索引頁(yè)面中出現(xiàn)了相同的key，所以需要用葉子頁(yè)面中下一個(gè)key，也就是12替換上層索引頁(yè)面中的7，最終的結(jié)果如下面圖(9)所示：
2. 葉子頁(yè)面填充因子50%，索引頁(yè)面填充因子大于等于50%
葉子頁(yè)面填充因子小于50%的時(shí)候，為了維持B+樹(shù)的平衡，會(huì)有頁(yè)面數(shù)據(jù)轉(zhuǎn)移和合并的操作
從兄弟頁(yè)面轉(zhuǎn)移key數(shù)據(jù)到當(dāng)前頁(yè)面
當(dāng)一個(gè)葉子頁(yè)面填充因子小于50%，左右兄弟頁(yè)面存在填充因子大于50%的時(shí)候，可以把兄弟頁(yè)面中的數(shù)據(jù)轉(zhuǎn)移到當(dāng)前頁(yè)面中，上一層索引頁(yè)面中因葉子頁(yè)面數(shù)據(jù)轉(zhuǎn)移受影響的索引key也需要做相應(yīng)的處理
如果左右兄弟頁(yè)面的填充因子都大于50%時(shí)，轉(zhuǎn)移任何一邊頁(yè)面數(shù)據(jù)到當(dāng)前頁(yè)面都可以，雖然選擇不同的頁(yè)面轉(zhuǎn)移數(shù)據(jù)后，B+樹(shù)的形態(tài)不一樣，但是最終都是滿足B+樹(shù)特點(diǎn)的
上面圖(10)中，刪除key為16的數(shù)據(jù) ( 圖中紅色標(biāo)識(shí)的區(qū)域 )，刪除之后，原來(lái)key為15, 16的葉子頁(yè)面變成了 15 ,頁(yè)面只剩下一個(gè)key
此時(shí)頁(yè)面的填充因子小于50%，左兄弟頁(yè)面填充因子大于50%，滿足頁(yè)面數(shù)據(jù)轉(zhuǎn)移的條件
把左兄弟頁(yè)面 (key為 7, 12, 13 )中的 13 轉(zhuǎn)移到當(dāng)前頁(yè)面中
轉(zhuǎn)移之后，兩個(gè)頁(yè)面key數(shù)量剛好等于填充因子，左兄弟頁(yè)面key變?yōu)?nbsp;7, 12,當(dāng)前頁(yè)面的key變?yōu)?nbsp;13, 15
當(dāng)前頁(yè)面中最小key值由原來(lái)的 15 變成了 13，為了保持B+數(shù)的平衡，需要把當(dāng)前頁(yè)面上一層的索引頁(yè)面中key為15替換為13， 最終的結(jié)果如下面圖(11)所示 :
當(dāng)前頁(yè)面key合并到兄弟頁(yè)面
上面說(shuō)明了從兄弟頁(yè)面轉(zhuǎn)移數(shù)據(jù)到當(dāng)前頁(yè)面，現(xiàn)在我們來(lái)看下當(dāng)前頁(yè)面數(shù)據(jù)量小于填充因子的時(shí)候，如何合并到兄弟頁(yè)面中
當(dāng)一個(gè)葉子頁(yè)面填充因子小于50%，左右兄弟頁(yè)面存在填充因子等于50%的時(shí)候，可以把這個(gè)葉子頁(yè)面合并到左右兄弟頁(yè)面中，上一層索引頁(yè)面中因葉子頁(yè)面數(shù)據(jù)合并受影響的索引key也需要做相應(yīng)的處理
在圖(12)中，執(zhí)行刪除key為15的操作（圖中紅色區(qū)域），15位于key為 13, 15 的頁(yè)面中，刪除15之后，當(dāng)前頁(yè)面key變成了 13, 只剩下一個(gè)key了
此時(shí)，當(dāng)前頁(yè)面填充因子小于50%，左右兄弟節(jié)點(diǎn)填充因子等于50%，所以無(wú)法從兄弟頁(yè)面轉(zhuǎn)移key數(shù)據(jù)到當(dāng)前頁(yè)面，但滿足當(dāng)前頁(yè)面數(shù)據(jù)合并到兄弟頁(yè)面的條件
左右兄弟頁(yè)面都滿足當(dāng)前頁(yè)面數(shù)據(jù)合并過(guò)去，選擇任一兄弟頁(yè)面都可以，雖然選擇不同兄弟頁(yè)面，會(huì)導(dǎo)致B+樹(shù)的形態(tài)也不一樣，但最終都是讓B+樹(shù)維持平衡，這里我們選則合并到左兄弟頁(yè)面
15 被刪除了之后，當(dāng)前頁(yè)面只剩下key為 13 的數(shù)據(jù)了
它合并到左兄弟頁(yè)面之后, 當(dāng)前頁(yè)面為空，需要移除上一層索引頁(yè)面中指向當(dāng)前頁(yè)面的索引key 13, 移除13的索引key之后， 索引頁(yè)面key由原來(lái)的 7, 13, 23 變成 7, 23
合并之后，左兄弟頁(yè)面key由原來(lái)的 7, 12 變成 7, 12, 13
最終的結(jié)果如下面 圖(13) 所示 ：
3. 葉子頁(yè)面和索引頁(yè)面填充因子都小于50%
當(dāng)葉子頁(yè)面和索引頁(yè)面填充因子都小于50%的時(shí)候，葉子頁(yè)面和索引頁(yè)面都會(huì)有數(shù)據(jù)轉(zhuǎn)移或者合并的操作
在圖(14)中，執(zhí)行刪除葉子頁(yè)面中key為12的數(shù)據(jù)(圖中紅色區(qū)域)，12 位于key為 7, 12 葉子頁(yè)面中，刪除 12 之后，當(dāng)前葉子頁(yè)面變成了 7,只剩下一個(gè)key了
當(dāng)前葉子頁(yè)面左右兄弟頁(yè)面填充因子都是50%，所以滿足合并的條件，合并到左兄弟頁(yè)面或右兄弟頁(yè)面都可以，這里我們選擇合并到左兄弟頁(yè)面
當(dāng)前葉子頁(yè)面中key為 7 的數(shù)據(jù)合并到左兄弟頁(yè)面之后，當(dāng)前葉子頁(yè)面沒(méi)數(shù)據(jù)了，而左兄弟頁(yè)面key變成了 2, 5, 7
為了保持B+樹(shù)的平衡，指向當(dāng)前葉子頁(yè)面的上一層索引頁(yè)面中，需要?jiǎng)h除key為 7 的索引key, 刪除key為7的索引后，索引頁(yè)面key變成了 15, 這時(shí)該索引頁(yè)面填充因子小于50%，右兄弟頁(yè)面填充因子等于50%，滿足合并的條件
但是，索引頁(yè)面數(shù)據(jù)合并到右兄弟頁(yè)面之后，根節(jié)點(diǎn)的左子樹(shù)就為空了，為了保持B+樹(shù)的平衡，根頁(yè)面數(shù)據(jù)需要合并到下一層的索引頁(yè)面中
最后的結(jié)果如下面圖(15)所示 :
范圍查詢
B+樹(shù)的葉子節(jié)點(diǎn)是按照key從小到大的順序組成的一個(gè)雙向鏈表，所以B+樹(shù)非常適合范圍查詢(這里說(shuō)的范圍是B+樹(shù)中索引節(jié)點(diǎn)的key的范圍)
使用二分查找首先確定范圍查詢的起始key所在的葉子節(jié)點(diǎn)的位置，然后順序遍歷葉節(jié)點(diǎn)鏈表，直到葉節(jié)點(diǎn)key大于范圍查詢結(jié)束key，查詢停止
B+樹(shù)的大小
一顆 m 階的B+樹(shù)，索引節(jié)點(diǎn)存儲(chǔ)的是索引信息，為了計(jì)算方便，這里假設(shè)一個(gè)索引key信息 8 字節(jié)，一個(gè)磁盤頁(yè)面大概 4KB，那么一個(gè)磁盤頁(yè)面能容納的索引數(shù)量為：4 * 1024 / 8 = 512，此時(shí) m 就等于 512
當(dāng)B+樹(shù)高度為2時(shí)，最多能容納 512 (512的1次方) 個(gè)索引信息
當(dāng)B+樹(shù)高度為3時(shí)，最多能容納 26萬(wàn) (512的2次方)個(gè)索引信息
當(dāng)B+樹(shù)高度為4時(shí)，最多能容納 1.3億 (512的3次方)個(gè)索引信息
當(dāng)B+樹(shù)高度為5時(shí)，最多能容納 687億 (512的4次方)個(gè)索引信息
從上面的數(shù)據(jù)可以看到，B+樹(shù)高度為5時(shí)， 能容納 687 億個(gè)索引信息，可以非常夠用了
在實(shí)際的應(yīng)用當(dāng)中，B+樹(shù)的根節(jié)點(diǎn)都是緩存在內(nèi)存中的，樹(shù)的最底層是葉子節(jié)點(diǎn)
所以針對(duì)高度為5的B+樹(shù)，查找一條指定key值的數(shù)據(jù)最多只需要3次磁盤IO就能定位到具體的葉子頁(yè)面，當(dāng)樹(shù)高度為4時(shí)，最多只需要2次磁盤IO就能定位到具體的葉子頁(yè)面
B+樹(shù)的應(yīng)用
B+樹(shù)主要用于磁盤和存儲(chǔ)工具，著名的MySQL引擎 InnoDB 索引的數(shù)據(jù)模型使用的就是 B+ 樹(shù)
當(dāng)數(shù)據(jù)超過(guò)一定的量級(jí)的時(shí)候，為了快速檢索數(shù)據(jù)而設(shè)置的索引信息也會(huì)變得非常龐大，而且這部分索引信息只能存儲(chǔ)在磁盤中，B+樹(shù)能從磁盤中快速檢索到需要的數(shù)據(jù)，并且時(shí)間復(fù)雜度穩(wěn)定在O(logn)