本文始發于個人公衆号：TechFlow，原創不易，求個關注
今天是周五分布式系統的第八篇文章，核心内容是B+樹的原理。
今天的文章是上周B樹的延伸，是以新關注的或者是有所遺忘的同學建議先從下方連結回顧之前的内容。
硬核挑戰——從零開始動手圖解B樹
B+樹的特性
B+樹和B樹一樣都是多路平衡樹，也叫多叉樹。兩者的性質也基本一緻，在具體來看詳細内容之前，我們先來總體看下B+樹的特性，先有個大概的印象。
我個人認為B+樹大部分特性都和B樹一樣，唯一不同的隻有以下幾點：
- 所有的資料都存儲在葉子節點，中間節點不存放資料
- 中間節點的元素數量和子樹數量一緻，而B樹子樹數量比元素數量多1
- 葉子節點是一個連結清單，可以通過指針順序查找
我貼一張圖，大家應該可以很直覺地感受到。
從上圖我們可以看到，所有出現在中間節點的元素都能在葉子節點當中找到，這對應了剛才說的所有資料都存放在葉子節點當中。然後我們還可以發現，中間節點當中的元素數量和子樹數量一緻，同樣對應了區間分割。父節點的每個元素對應了一個子樹中最大的元素。
至于最後的連結清單，應該很好了解，無非是連結清單出現在樹當中，看起來有些新奇而已。
我看上圖最大的感受就是像，和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 排版