今天是周五分佈式系統的第八篇文章，核心內容是B+樹的原理。

今天的文章是上周B樹的延伸，所以新關注的或者是有所遺忘的同學建議先從下方鏈接回顧之前的內容。

硬核挑戰——從零開始動手圖解B樹

B+樹的特性

B+樹和B樹一樣都是多路平衡樹，也叫多叉樹。兩者的性質也基本一致，在具體來看詳細內容之前，我們先來總體看下B+樹的特性，先有個大概的印象。

我個人認為B+樹大部分特性都和B樹一樣，唯一不同的只有以下幾點：

1. 所有的數據都存儲在葉子節點，中間節點不存放數據
2. 中間節點的元素數量和子樹數量一致，而B樹子樹數量比元素數量多1
3. 葉子節點是一個鏈表，可以通過指針順序查找

我貼一張圖，大家應該可以很直觀地感受到。

從上圖我們可以看到，所有出現在中間節點的元素都能在葉子節點當中找到，這對應了剛才說的所有數據都存放在葉子節點當中。然後我們還可以發現，中間節點當中的元素數量和子樹數量一致，同樣對應了區間分割。父節點的每個元素對應了一個子樹中最大的元素。

至於最後的鏈表，應該很好理解，無非是鏈表出現在樹當中，看起來有些新奇而已。

我看上圖最大的感受就是像，和B樹實在是太像了，就好像兩個孿生兄弟，猛地看上去幾乎一模一樣，細微分辨才能發現一點差別。那麼針對這樣一顆熟悉又陌生的樹，我們應該怎麼去增刪改查呢？

讓我們繼續往下看，在此之前，我想說一句，雖然B+樹是B樹的提升版，但是實現難度上，其實是降低的。也就是說整體而言，它比B樹更容易實現。

B+樹的查

由於B+樹當中所有的數據都存儲在葉子節點，所以我們在查找的時候，必須要一直查找到葉子節點為止。也就是說不會再有中途退出的情況，這樣就簡化了我們的判斷，幾乎不再需要臨時退出了。

另一個特性是B+樹當中的元素數量和子樹數量一致，並且每個元素都代表一棵子樹當中的最大值。通過這個限制，我們可以很輕鬆地確定我們要查找的元素究竟在哪棵子樹當中。而B樹則有可能出現超界的情況，我們需要特殊判斷。

舉個例子，這是一棵B樹：

假設我們查找的元素是12，我們在根節點當中判斷，先通過二分查找查找到9，發現12 > 9，於是我們去最右側的子樹當中檢查。

而如果是B+樹，會是這樣，為了作圖方便，我省去了葉子節點中橫向的指針。

可以看到我們直接二分就可以精準地找到對應的子樹，我們直接往下遞歸就好了。如果超界了，則說明肯定不在樹上，可以提前返回。

所以這就是一個非常簡單的樹上查找，應該說只要理解了樹的形狀和遞歸的思路，應該是沒有難度的。不過有一點需要注意，我們的查找接口並不只提供給外部，我們自己在插入的時候也會需要先找到對應的位置（節點）再執行插入的。顯然我們要插入的元素十有八九不在樹上（不然還叫什麼插入），這個時候就不能返回空了，我們需要返回一個實實在在的節點。

所以我們可以傳入一個flag，標記是否是我們內部調用的插入階段，flag默認是False，所以對外部調用沒有影響。

如果flag是True，我們在中途沒有找到的時候就不能提前退出了，需要繼續查找。並且我們還有可能更新一下最右側元素的值。

還用上圖舉個例子：

如果我們插入一個元素15，整棵樹會變成：

看到了嗎，根節點當中的12被替換成了15，這也對應上了之前說的節點中的每個元素都對應子樹中的最大值。我們先插入再去更新父親當然也是可以的，但我們也可以在查找的時候直接進行更新，當我們發現待插入的元素比當前節點最大的元素還要大時，直接進行替換，這樣可以省去一些代碼。

我們來看下代碼：

 def _query(self, node, key, flag=False):
 """
 :param node: 當前節點
 :param key: 待尋找的key
 :param flag: 是否是插入階段
 :return: True/False 是否找到，對應的節點，key在節點中的下標
 """
 # 如果是葉子節點，說明沒有childs
 if node.is_leaf:
 # 校驗當前是否為空
 if node.length == 0:
 return False, node, 0
 # 二分查找
 pos = bisect_left(node.keys, key)
 # 如果沒找到，返回False
 if pos == node.length or node.keys[pos] != key:
 return False, node, 0
 else:
 return True, node, pos
 else:
 pos = bisect_left(node.keys, key)
 # 遞歸
 if pos == len(node.childs):
 if not flag:
 return False, node, 0
 else:
 # 如果是插入階段，待插入的元素大於所有元素
 # 直接替換最後一個元素
 node.keys[-1] = key
 pos -= 1
 return self._query(node.childs[pos], key, flag)

大家應該都注意到了B+樹的葉子節點是一個鏈表，每個節點都有一個next指針指向它的右兄弟。所以我們也可以通過鏈表來查找元素，這段代碼並不難寫，就是一個簡單的鏈表遍歷，當中涉及的細節不多，我們直接來看代碼：

def seq_query(self, key):
 node = self.head
 # 循環遍歷鏈表
 while node is not None:
 # 二分查找是否在當前節點
 pos = bisect_left(node.keys, key)
 # 如果大於當前的所有元素
 if pos == node.length:
 # 如果沒有後續了說明沒找到
 if node.next is None:
 return False, None
 node = node.next
 continue
 # 如果找到了判斷是否是我們要的
 if node.keys[pos] == key:
 return True, node.values[pos]
 else:
 return False, None

B+樹的增

第二個方法是添加元素，添加元素的邏輯和B樹基本一致，只是有些細微的變動。

和B樹一樣，B+樹的所有插入操作也都發生在葉子節點。所以我們通過查找操作找到適合插入這個元素的節點，進行插入。由於B+樹對節點上元素的數量進行了限制，最多不能超過M個，也就是說插入操作可能會引起非法，所以我們需要對這種情況進行判斷，如果插入會導致非法，我們需要採取措施維護數據結構的性質。

採取的措施很簡單，和B樹一樣，如果節點元素數量超標，那麼進行分裂。

但是它的分裂操作會有一點細微的差別，我們一起來看：

假如這是一顆4階的B+樹，那麼當我們插入一個元素之後，它就會發生分裂。比如我們插入5，可以得到：

注意到了嗎，由於分裂會產生兩棵子樹，所以分裂之後上層的節點會有兩個元素，而B樹只有一個元素。

但如果分裂不是發生在根節點，那麼還是只會上傳一個元素，和B樹一樣。

再來看一個例子：

如果此時我們加入元素12，第三個子樹的元素數量會超標，於是會發生分裂：

我們最後一個節點插入元素之後發生了分裂，但是只上傳了10進入了父親節點當中，因為15本來就已經在父節點當中了，沒有必要上傳。

當然這個圖不是最終的形態，根節點顯然也超過了限制，需要進一步分裂，最後變成這樣：

當然這個只是整體的邏輯，在我們實現的過程當中還有很多細節需要考慮。比如當前節點是否是葉子節點？如果是葉子節點，那麼它沒有子樹需要分裂，但是會有value需要分裂。如果不是葉子節點，它分裂了之後，我們還需要維護它的childs以及底層的鏈表，不過這些細節雖然多，但是其中的邏輯並不複雜，只要我們實現的時候把所有的細節梳理清楚，以及做好系統的測試，這並不困難。

這裡着重提一下分裂時候next指針的處理，假設當前的bt_node是一個葉子節點，當它發生分裂的時候，會生成兩個新的節點，我們命名為lnode和rnode。之後我們需要將bt_node升入父節點和父節點合併，這個時候我們怎麼維護next指針呢？

我們可以很隨意想到應該讓lnode的next指向rnode，rnode的next指向node的next，但是怎麼讓bt_node之前的next指向lnode呢？

一個辦法是我們可以在函數當中將node的左兄弟也傳進來，但是這樣會需要很多操作。比如我們需要先找到左兄弟，這個尋找其實並不容易，因為可能左兄弟和它不在一棵子樹，而且還需要判斷左兄弟不存在的情況。所以還是很麻煩的，或者我們可以多存一個指向左邊的指針，這樣就可以很方便地找到左兄弟了。我想到的一個辦法是利用Python當中引用存儲的trick來避免這些複雜的操作。

我們假設這個左兄弟節點是brother，在brother的next當中存儲了bt_node的引用，也就是node在內存當中的地址。取巧的辦法就是讓lnode等於bt_node，也就是用lnode引用指向bt_node，之後再將lnode當中的值手動更新成我們需要的。這樣通過取巧的辦法，就繞開了這個問題。我們看下代碼：

bt_node_next = bt_node.next
lnode = bt_node
# 手動更新lnode
lnode.update()
rnode = BTree.BTreeNode(keys=rkeys, childs=rchilds, is_leaf=bt_node.is_leaf, father=node, pos_in_father=1, values=rvals)
lnode.next = rnode
rnode.next = bt_node_next

這段代碼不難，但是這個trick不太容易想到，需要對Python的引用機制有一定的了解。這個只是實現的取巧，和算法關聯不大，看不懂的同學可以忽略。

理解了這些之後，我們最後來看下B+樹的刪除。

B+樹的刪除

B+樹的刪除邏輯和B樹完全一致，只是具體操作的細節有略微的區別。

和B樹一樣，所有的刪除全部都發生在葉子節點，但是由於B+樹所有的元素都存在葉子節點，所以我們不存在需要考慮刪除中間節點並且用後繼來替代的情況。我們直接查找到葉子節點進行刪除和維護即可。不得不說這一點上要簡化了許多。

直接刪除

和B樹一樣，如果葉子節點元素數量富裕，那麼直接刪除。

比如我們要刪除上圖當中的13，由於葉子節點富裕，所以直接刪除即可，得到：

這點沒什麼好說的，但是如果我們刪除的是15，雖然也是直接刪除，但是就會有點問題。我想大家應該也發現了，就是15不僅是葉子節點當中的一個，而且還出現在中間節點上，如果我們刪掉了15，那麼顯然需要更新這一條鏈路上的節點。

我們需要一路回溯上去，將它們的值都改成刪掉15之後最大的值，這裡的這個細節和B樹不太一樣，需要注意。更新之後的結果應該是這樣的：

我們往上回溯的時候也需要判斷，之後修改的節點是父節點中最大的值才需要回溯，因為父節點中最大的值也在父節點的父節點裏，如果不是只需要修改即可，不再需要回溯，我們來看代碼：

def upload(self, bt_node, father, key):
 if father is None:
 return
 # 修改父節點中值
 father.keys[bt_node.pos_in_father] = key
 grand_fa = father.father
 # 如果修改的是父節點中最大的值，繼續往上回溯
 # 因為父節點中的最大值也在爺爺節點中
 if bt_node.pos_in_father == father.length-1 and grand_fa is not None:
 self.upload(father, grand_fa, key)

這裡有一個很有意思的點，就是我在一開始實現的時候忘記了需要持續回溯這茬，只考慮了更新父節點，沒有一直往上回溯。但是我用了一大批數據進行測試，發現仍然是正確的。

我後來仔細思考了一下，發現的確沒有必要一直回溯上去。因為我們在查找的時候，在上層節點並不能斷定元素是否存在。比如上面的例子，如果我只回溯了一層，沒有回溯到頂層。這棵樹會是這樣：

也就是說根節點當中存的仍然是15，但是15此刻已經被刪除了。其實並不影響我們的搜索，因為樹上已經不存在比15大的元素了，我們在頂層用15來二分和用13來二分的結果都是一樣的，就是往右側的子樹遞歸。而往下遞歸了之後，數據就正確了，所以我們只用更新葉子節點往上一層即可。但是這只是我的判斷，我暫時沒有想到反例，歡迎有想法的同學給我留言。

兄弟節點富裕

兄弟節點富裕，很簡單我們和兄弟節點借就行，和B樹不一樣，由於所有的節點都在葉子上，我們可以直接將兄弟節點的元素借過來，但是需要注意更新父親節點中的值。

舉個例子，比如說我們要刪除下圖中的4，我們發現它的左兄弟有富裕的元素，我們不再需要通過父節點中轉，可以直接借過來。

但是借過來之後，會有一點小問題，就是父節點中的3就失效了，因為它不再是左側子樹中最大的元素了，最大的元素變成了2。所以我們需要更新父節點中這個值。我們和右側兄弟借元素也是一樣，只是方向不同，我就不再贅述了。

兄弟節點不富裕

最後，我們來看下兄弟節點也不富裕的情況。這點和B樹類似，但是略有不同。在當下場景當中，我們不再向父節點強行借元素了，想想也能明白，父親節點當中的數據都在葉子上，還有什麼好借的呢？所以我們不借元素，直接和兄弟節點合併。

比如在下圖當中，如果我們要刪除元素12，會導致違反限制，這個時候我們直接合併紅框當中的兩個節點。

合併之後會帶來子樹的數量減少，所以我們要remove掉父節點當中的一個元素。我們對照一下上圖，可以發現，我們要刪除父節點當中的10。這裡我們要判斷一下，如果和當前節點合併的是左兄弟，那麼我們要刪除的是左兄弟的最大值，否則是右兄弟的最小值。刪除之後，維護父節點，我們發現父節點不再滿足條件，需要維護。

顯然它沒有富裕的兄弟節點，於是我們繼續合併：

同樣的操作之後，我們發現當前節點的父節點也就是根節點只剩下了一個元素，這是非法的，於是我們需要將它拋棄，更新根節點。

後記

到這裡，我們B+樹的增刪改查也就介紹完了，說起來非常恐怖的數據結構，但用圖展示出來也就只有這麼幾張，我完整寫出來的代碼不超過500行，並不是一個非常嚇人的數字。很多時候我們恐懼數據結構當中的變形、旋轉等操作，但其實靜心畫出所有的變化，來來回回也就那麼幾種。當我們抗拒和退縮的時候，並不是數據結構或者是難題戰勝了我們，是我們自己放棄了。

最後，我們來思考一個問題，為什麼B+樹當中把所有元素都放在葉子節點是一種優化呢？難道這樣不是增加了查找的負擔嗎？我們之前可能在半途就查到了元素，現在一定要查找到結尾才行，這怎麼算是優化呢？

同樣，回答這個問題，光理解數據結構是不夠的，我們還需要結合使用場景。B+樹的場景我們都知道，是數據庫的底層實現結構。我們都知道數據庫當中的數據非常龐大，我們不可能將所有的數據都存在內存當中。而磁盤的隨機讀寫是非常耗時的，我們把所有數據都放在葉子節點，對於大量新增和刪除的情況，我們可以將獲得連續的數據進行批量操作，可以大量節省時間。另外B+樹對於批量讀取的效率比B樹更高，比如我們要讀取一個區間，可以先查找到一個節點之後，通過next指針往後批量獲取。我們通過指針的遍歷操作是順序讀寫，讀寫速度要比隨機讀寫快得多。

也就是說B+樹的優化體現在磁盤讀寫上，而不是算法上。當然從整體的實現難度上來說，B+樹確實也要更簡單一些。如果對源碼感興趣的同學可以在公眾號回復「B+樹」，獲取我的代碼，請不要嫌棄。

今天關於B+樹的分享就到這裡，如果覺得有所收穫，麻煩順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。

本文使用 mdnice 排版