豐富圖文詳解B-樹原理，從此面試再也不慌

2020 年 3 月 7 日
筆記

本文始發於個人公眾號：TechFlow，原創不易，求個關注

本篇原計劃在上周五發布，由於太過硬核所以才拖到了這周五。我相信大家應該能從標題當中體會到這個硬核。

周五的專題是大數據和分散式，我最初的打算是和大家分享一下LSM樹在分散式存儲引擎當中的應用。但是想要能夠真正深入理解了LSM的精髓，以及它構思巧妙的點，必須要對傳統的資料庫的B樹和B+樹有所了解。所以才有了今天的文章。

雖然我自己完整地將B樹寫了一遍，但是我並不建議初學者這麼干，強行啃太難的數據結構除了容易勸退之外基本上沒有太大的幫助。所以，雖然我起了這麼一個標題，但是我並不會在文章當中貼太多的程式碼。而且即使是面試FLAG，只要不作死在簡歷里寫自己是ACMer，一般也不會碰到讓手寫各種樹的面試題。因此，相比於親自實現，我們能夠理解原理更加重要。

即使你是初學者，對於數據結構了解不多，也請不要退出，我有信心讓你能夠理解清楚B樹的運行原理。

二叉與二叉搜索樹

在詳解原理之前，我們先複習一下簡單的概念。

首先來看二叉樹的概念，二叉樹的概念本身很簡單，除了根節點之外，每個節點最多有兩個孩子。

比如這樣一棵樹就是一顆二叉樹：

二叉樹本身並沒有太多用處，只是一個樹形的數據結構而已，直到後來有大神想到了一個trick。如果我規定一顆二叉樹上的元素擁有順序，所有比它小的元素在它的左子樹，比它大的元素在它的右子樹，那麼我們不就可以很快地查找某個元素了嗎？

不得不說這是一個非常天才的想法，於是，二叉搜索樹誕生了。

上圖就是一個經典的二叉搜索樹，比如我們要查找元素4，首先和根節點8進行比較。顯然4 < 8，那麼迭代到8的左子樹3，4 > 3，於是往3的右子樹走，走到6。4 小於6，於是走到了6的左子樹，也就是4，我們找到了元素，結束。

在理想情況下，二叉樹每多一層，可以存儲的元素都增加一倍。也就是說n個元素的二叉搜索樹，對應的樹高為(log(n))。所以我們查找元素、插入元素的時間也為(log(n))。

不過這是理想情況，顯然在實際使用當中很有可能情況並不那麼理想。舉個簡單的例子，如果插入的數據按照遞增或者遞減的順序出現，那麼所有的元素會線性排列，樹形結構會退化成鏈表。顯然在這種情況下，查找和插入的效率會蛻化成(O(n))。在演算法領域可以接受一個數據結構不完美或者是絕大多數情況下可靠，但是不能接受可靠性未知。

為了解決二叉搜索樹不平衡的問題，在此基礎上提出了各種平衡樹。比如數據結構課本上的AVL就是一顆經典的平衡樹，平衡樹的思路很樸素，就是在插入元素的時候進行判斷，如果當前的元素的插入或刪除會影響樹的平衡性，那麼則進行旋轉操作，從而維持樹的平衡。

正是因為引入了旋轉的機制，才保證了二叉搜索樹的性能，也因此大大提升了這個原本很簡單的數據結構的難度。

上圖就是一個經典的旋轉操作，在增刪改查操作當中，經常要用到旋轉操作平衡整棵樹，也因此對於程式設計師的邏輯和空間思維要求比較高。對初學者容易勸退。這裡我們不深究旋轉的細節，在B樹當中不會用到旋轉，我們只需要知道它是用來調整樹的結構來重新構成平衡的就行了。

二叉和多叉

二叉搜索樹理解了，多叉搜索樹也就順理成章了，根本原理是一樣的，唯一的不同是多叉搜索樹允許節點中的元素數量超過1。也就是一個節點可以存儲多個元素，並且會有多個子樹分支。

在B樹當中有一個非常巧妙的設計，就是每一個節點的孩子個數是元素的數量+1。並且和二叉搜索樹一樣，存在大小順序的關聯。

如圖，根節點有兩個元素3和9，並且有3個孩子節點，剛好對應了3個區間。分別是小於3的，在3和9中間的以及大於9的，那麼根據我們要查找的元素的大小，我們很容易判斷究竟應該選擇哪一個分支。而且節點中的元素是有序的，我們可以使用二分查找進行高效搜索。

我們來思考一個問題，既然二叉搜索樹也可以完成節點的高效增刪改查，我們為什麼又需要搞出這個多叉搜索樹呢？和二叉搜索樹相比，它究竟有什麼得天獨厚的優點呢？

我們光看是看不出來的，需要了解一下B樹實際的應用場景。B樹主要用在各大存儲文件系統和資料庫系統當中。在這些場景下數據總量很大，我們不可能將它們都存儲在記憶體當中。所以為了解決這個問題，我們會在樹節點當中存儲孩子節點的在磁碟上的地址。在需要訪問的時候通過磁碟載入將孩子節點的資訊讀取到記憶體當中。也就是說在資料庫當中我們遍歷樹的時候也伴隨著磁碟讀取。

我們之前介紹MapReduce的時候曾經說過，磁碟的隨機讀寫是非常耗時的。顯然，樹的深度越大，磁碟讀寫的次數也就越多，那麼帶來的IO開銷也就越大。所以為了優化這個問題，才設計出了B樹。由於B樹每個節點存儲的數據和孩子節點數都大於2，所以和二叉搜索樹相比，它的樹深要明顯小得多。因此讀寫磁碟的次數也更少，帶來的IO開銷也就越小。這也是它適合用在文件引擎以及資料庫引擎上的原因。

我們來看一張圖，直觀地感受一下：

從上面這個例子我們可以看出來，同樣的元素，明顯B樹的樹深更小。

B樹的定義

雖然B樹是一棵多叉搜索樹，但是並不意味著只要是多叉搜索樹就是B樹。B樹對節點同樣存在著一些限制，每個節點能夠存儲的元素以及孩子節點數量並不是隨意的。

我們來看具體的定義：

B樹中每個節點的元素數量和子樹的數量都是有限的，除了根節點外，所有節點最多擁有M-1個元素，所有非葉子非根節點最多擁有M個子樹（稱為M階B樹）
根節點至少擁有兩個子樹，除了根節點之外的非葉子節點擁有K個子樹以及K-1個元素((M+1/2) < K < M)，元素按照遞增或遞減順序排列
所有葉子節點屬於同一層

也就是說B樹就是通過獨特的機制來實現增刪改查，使得增刪改查之後的結果依然滿足上面這三點。雖然說是增刪改查，但是改和查的邏輯其實是一樣的。所以其實只有三個核心的方法。

在介紹具體的機制之前，我們再強調一遍，從原理上來說B樹並不複雜，並且不涉及樹的旋轉操作，也沒有複雜的變換。

B樹的查找

我們按照老規矩，先從最簡單的開始介紹。其實不論什麼搜索樹，最簡單的部分幾乎一定都是查找。因為查找操作不會改變樹結構，我們只需要理解查找的邏輯即可。

B樹的查找和二叉樹的查找本質是一樣的，可以把二叉樹看成是B樹的一種特殊情況。

查找操作的本質其實就是通過對當前節點元素的判斷，來縮小查找的範圍。我們前面已經介紹過了，B樹當中一個節點對應的K個子樹和它K-1個元素是對應的。我們只需要判斷查找的key和當前節點所有元素的大小關係就可以判斷數據的範圍。

為了簡化說明，我們先定義一下B樹當中的節點：

class Node:      def __init__(self):        self.keys = []        self.childs = []

B樹的一個節點當中有K-1個元素以及K個子樹，我們用keys和childs來存儲。並且我們知道，keys當中的元素是有序的。childs中的子樹對應keys中元素分隔得到的區間。

我們假設我們要查找的元素是key，當前的節點是node。

首先我們查找node.keys當中大於等於key的位置，我們命名為pos。如果pos等於len(node.keys)或者node.keys[pos] != key，說明當前節點不是我們要找的，我們要繼續搜索子樹。

這個子樹是什麼呢？其實就是node.childs[pos]，因為我前面說了我們在node.keys當中查找第一個大於等於key的，而node.keys[pos] != key，那麼顯然node.keys[pos] > key或者是key比node.keys當中的所有元素都要大，這樣pos會是len(node.keys)，也是node.childs[-1]，所以不論是哪種情況，我們訪問node.childs[pos]都是正確的。所以我們遞歸調用，否則的話說明node就是目標，我們直接返回。

舉個例子：

比如我們要搜索7，首先我們在根節點當中找到第一個大於等於7的位置，這個位置的元素是9不等於7，說明當前節點當中沒有7，我們需要繼續往子樹遞歸查找。由於子樹對應元素分割出來的區間，所以我們可以確定如果7存在子樹當中，只會出現在9前面的子樹中，所以我們往9的下標的子樹，也就是node.childs[1]的子樹方向遞歸。

我們來看下程式碼：

 def _query(self, node, key):          """            :param node: B樹的節點          :param key: 待查找的目標          :return: True/False 表示是否找到， node表示對應的B樹節點，以及key在node當中的下標          """          # 如果節點是葉子節點，那麼說明它沒有childs          if node.is_leaf:              # 判斷是否存在元素              if node.length == 0:                  return False, node, 0              # 二分查找key的位置              pos = bisect_left(node.keys, key)              # 如果不在node當中，返回False              if pos == node.length or node.keys[pos].key != key:                  return False, node, 0              else:                  return True, node, pos          else:              # 如果不是葉子節點              pos = bisect_left(node.keys, key)              # 沒找到的話就繼續遞歸              if pos != node.length and node.keys[pos].key == key:                  return True, node, pos              return self._query(node.childs[pos], key)

我們用到了一個叫做bisect_left的函數，它源於Python當中的二分查找庫bisect，可以代替我們實現二分查找，返回第一個大於等於key的位置，如果都比它小，則返回數組的長度。

B樹的插入

和查找相比，B樹的插入要複雜一些。

B樹的插入有一個原則，那就是所有的插入操作只發生在葉子節點。這點其實很容易想明白，因為如果要插入的key在非葉子節點，那麼這就變成了修改操作了，我們直接修改原key對應的value。如果插入的key不在非葉子節點，那麼顯然我們可以一直查找到葉子節點。

比如這張圖當中，3-9的根節點將整個區間分割成了小於3，3到9和大於9這三個區間。無論我們要插入的key是什麼，要麼落在區間邊界，要麼落在某個區間里。落在邊界的情況就是key值出現在了非葉子節點的keys當中，我們直接修改它對應的value即可，如果出現在區間里，那麼顯然應該在葉子節點當中添加一個值。

但是往葉子節點當中添加數據有一個小問題，那就是B樹對於所有節點當中元素的數量是有限制的，不允許無限添加。所以我們需要對節點中元素超過數量的情況做處理。

B樹針對這個問題的解決方案非常巧妙，它的措施很簡單，用一句話概括就是通過分裂節點來減少節點當中元素的數量。

有一個問題是我們分裂了節點之後，父節點當中的元素也應該增加才對，因為父節點的子樹數量是和節點中元素的數量對應的。子節點分裂導致分支增加，那麼顯然父節點也應該增加一個元素才對。

的確如此，也是因為這個原因，所以葉子節點分裂之後，需要上傳一個元素到父節點當中，來保證父節點中元素數量和子樹數量保持合法。我們來看下面這個例子：

這是一個4階的B樹，我們先插入5，這時候中間葉子節點的元素數量達到3，這時還沒有違反性質。我們再插入6：

這時葉子節點在連續插入兩個元素之後數量大於等於M，那麼我們需要將它一分為二，將中間節點上傳給父節點。於是經過這個調整之後，父節點當中增加了一個元素，也增加了一個分支，保證了B樹繼續合法。

最後得到的結果如下：

但是你可能會問，那父節點當中上傳了一個元素也可能導致父節點中元素數量超標啊，對於這個問題該怎麼辦呢？其實很簡單，和你想的一樣，我們繼續分裂節點。

來看下面這個例子：

我們往其中插入13，會導致最後一個葉子節點數量超標，於是我們分裂節點，將中間元素11上傳到父節點：

但是由於上傳父節點也可能引起元素數量超標，所以我們要向上遞歸判斷是否需要分裂節點的操作。此時父節點當中元素數量大於等於M，需要繼續分裂：

分裂產生新生成的節點由於高度更高，代替了原本的根節點，成為了新的根節點。並且原來根節點的子樹也發生了拆分，分別分配給新根節點的兩個子樹。也就是說我們在拆分節點的時候，除了要拆分keys之外，也需要拆分childs，並且將這些childs重新assign父指針。

B樹的刪除

到這裡就到了整個數據結構最難的部分了，它的難點並不在於演算法本身，而在於情況初看起來比較多，顯得比較複雜。但在這個問題下所有的變化都是有跡可循的，我們只需要把握住變化的根本原因以及目的，這些看起來複雜的變化都不再是問題。

所有刪除的都是葉子節點

首先，我們來理清楚第一個要點。無論我們當前刪除的元素是什麼，最終都會落實在葉子節點上，也就是說所有的情況都可以轉化成刪除葉子節點的問題。

我知道這聽起來很荒謬，因為很有可能我們要刪除的元素並不在葉子節點，而在中間的某棵子樹的根節點，怎麼能說都能變成葉子節點的刪除呢？

做到這點並不難，只需要我們做一個很簡單的轉化。

我們舉個例子，在下面這張圖中，假如我們要刪除元素11，而11在根節點上，顯然我們要刪除的位置並不在葉子節點。

但是為了避免刪除非葉子節點的元素，我們可以先找到11的後繼節點。這裡的後繼節點指的是在這棵樹上，比當前元素大的最小的節點。在這個圖當中，11的後繼節點是12，我們將12賦值給11，遞歸往下調用，轉變成刪除12，如圖2：

當然，我們選出來的後繼節點仍然可能並不是葉子節點，這沒有關係，我們只需要重複執行以上操作即可。因為我們可以保證後繼節點出現的位置在樹上的深度只會比當前元素更大，不會更小。而樹深是有限的，也就是說最多經過有限次轉化，我們就可以把刪除操作轉嫁到葉子節點身上。

這一點是後續所有推導的前提，我們必須要搞清楚。

後繼節點的求法

求後繼節點是二叉搜索樹當中非常常規的做法，思路本身很樸素，就是找到比某個key值大的最小的節點。本質上來說就是二分搜索當中的upper_bound。

但是在樹形節點上做這個操作會多一點步驟，沒有二分法那麼直觀。對於一個節點來說，如果當前節點沒有元素大於key，那麼只有一種可能：後繼節點在最右側的子樹上。因為最右側的子樹大於節點中所有的元素，所以可能出現比key大的值。

舉個例子：

比如我們要求11的後繼，對於根節點而言沒有元素大於11，那麼如果這個後繼存在，必然在最右側的子樹當中。如果我們要求的是15的後繼，那麼顯然即使我們搜索了最右側的子樹，也找不到合法的後繼。

如果當前節點存在大於key的元素，那麼有兩種可能，一種可能是後繼出現在子樹上，還有一種可能是後繼就在這個節點當中。

還是上面的圖，如果我們要找10的後繼，我們在根節點當中找到了比10大的11，但是我們此時還沒有搜索子樹，所以沒有辦法判斷最後的答案是11還是子樹當中有更優的解。

所以為了解決這個問題，我們需要將11這個元素作為備胎，傳遞給子樹。如果子樹找到了更優的解，那麼就返回最優解，否則說明備胎就是最優解，那麼就返回備胎。

我們寫下偽程式碼：

def successor(node, key, backup):      # 查找第一個大於key的元素的下標      pos = binary_search(node.keys, key)      # 如果是葉子節點，那麼不用繼續遞歸了      if node.is_leaf:          # 找到則返回，因為子樹里的元素都比backup小          if pos < len(node.keys):              return node.keys[pos]          else:              return backup      # 沒找到則遞歸      if pos == len(node.keys):          return successor(node.childs[-1], key, backup)      # 找到了，更新備胎      backup = bt_node.keys[pos]      # 可能還有更好的，繼續遞歸，傳入新的備胎      return successor(node.childs[pos], key, backup)

刪除之後的兩種情況

在理解了這個問題之後，我們就可以愉快地討論節點上的元素情況了。

之前我們說過了，一棵合法的B樹，它葉子節點上的元素應該是K-1個，其中M//2 <= K <= M。

由於B樹存在最少節點數的限制，所以伴隨著我們刪除元素，很有可能打破這個限制。針對這一情況，我們進行分別討論。

假設葉子節點當中元素數量很多，我們刪除一個仍然可以保證它是合法的。這種情況很簡單，沒什麼好說的，直接刪除即可。

詳情參考下圖：

在上圖當中，M=4，也就是說我們最多允許一個節點出現4個分支，一個節點最少擁有4/2 – 1，也就是一個元素。

假如我們要刪除的元素是19，由於節點3當中元素眾多，即使刪除掉一個元素，依然符合節點的要求，那麼就不做任何操作。但如果我們刪除的是10，由於節點10隻有一個元素，如果刪除了，那麼就會破壞節點的最小元素數量的限制。

在這種情況下，只有一個辦法，就是先刪除，再和其他節點借。

和兄弟節點借

我們首先考慮和節點的兄弟節點借一個元素，這個思路很樸素。因為兄弟節點和當前節點的父親節點相同，可以很方便地轉移節點並保證樹的性質。

顯然對於一個葉子節點來說，它的兄弟節點最多只有兩個，也就是它左側的兄弟和右側的兄弟。由於B樹上的元素存在從左往右的遞增性，我們認為右側的是哥哥節點，左側的是弟弟節點。其實借的順序雖然會影響樹的形狀，但是並不會影響樹的合法性。所以我們先和哥哥借再和弟弟借，或者是反過來都行。我個人是設置的先哥哥後弟弟的順序。

還用之前的例子舉例：

假設我們要刪除節點10，節點10隻有一個元素，刪除了必然破壞合法性。這個時候我們先看下哥哥的情況，哥哥節點當中有3個元素，即使借走一個仍然可以滿足要求，那麼我們就和哥哥借。

借的方法很簡單，由於哥哥節點當中所有的元素都大於當前節點，所以顯然為了保證元素順序，我們會借第一個元素，也就是13。但是13是大於父節點中的12的，所以我們不能直接把13塞到原來10的位置，而需要先將父節點的12挪下來，放到10的位置，再將13填到12的位置上去。如果你熟悉平衡樹的話，你會發現這其實是一個左旋操作，如果你不熟悉的話，也不用糾結。

最後達到平衡態的樣子如下：

同理，如果我們要刪除的是23，由於它沒有哥哥節點，只有弟弟節點，並且弟弟節點滿足條件。那麼我們就和弟弟節點借一個元素，邏輯和上面一樣。我們先從父節點要一個元素下來，再從弟弟節點借一個元素放回父節點。得到的結果如下：

兄弟節點也是窮光蛋

既然存在兄弟節點可以借那麼顯然也會存在兄弟節點借不了的情況，如果兄弟節點自身也是勉強達到條件，顯然是借不了的。這種時候沒辦法，只能還是和父親節點要。如果父親節點稍稍富裕，給出了一個元素之後還是能滿足條件，那麼就從父親節點出。但是這裡需要注意，父親節點給出去了一個元素，那麼它的子樹數量也應該隨之減少，不然也會不滿足B樹的特性。為了達成這一點，可以通過合併兩個子樹來實現。

我們來看個例子，會更直觀一些，比如在下圖當中，我們繼續刪除10：