---

搜索結構

• 如果我們有大量的數據需要永久存儲，就需要存儲到硬盤之中。
• 但是硬盤的訪問速度遠遠小于內存，并且由于數據量過大，無法一次性加載到內存中。

此時，就可以考慮將數據存儲在硬盤中，而數據的地址則加載到內存中，通過某種搜索結構進行存儲，使用時只需要通過該結構查找到地址，在通過地址去找到對應的數據即可。

常用的幾種搜索結構：二叉搜索樹、AVL樹、紅黑樹、哈希、位圖、布隆過濾器。

考慮到查找性能以及內存消耗，其中適合這種場景的只有平衡二叉搜索樹（AVL、紅黑樹）。

但即使平衡二叉搜索樹的搜索性能能達到 O(log₂N)，由于數據量過于龐大，例如存儲了 10億個數，則可能最多需要查找 30次。這個數字看起來不是很多，因為之前我們比較的是內存的速度，即使是 10億個數 也能一瞬間查找完。但是對于硬盤來說，由于硬盤的速率低，每一次 IO 都意味這大量的損耗，所以這種方法也不太合適。

如果想要提高查找的效率，那么唯一的方法就是壓縮樹的高度，而壓縮的方法，就是將二叉樹變為 M叉樹，也就是使用到 M路平衡搜索樹——B樹。

---

B樹

B樹 即一棵平衡的 M路平衡搜索樹（M > 2），可以是 空樹 或者滿足以下性質：

• 根節點至少有 2 個孩子、最多有 M 個孩子；
• 除根結點外的非葉節點有 i 個孩子， M/2(上取整) <= i <= M；
• 每個非葉節點有 j 個關鍵字， M/2-1(上取整) <= j <= M-1 ，并且以升序排列；
• key[i] 和 key[i+1] 之間的孩子節點的值介于 key[i]、key[i+1] 之間；
• 所有的葉子節點都在同一層。

對照一棵 M=3 的 B樹 來理解：

節點實現

template<class K, int M = 3>
struct BTreeNode
{K _keys[M]; // 存放元素BTreeNode<K, M>* _pSub[M+1]; // 存放孩子節點，注意：孩子比數據多一個BTreeNode<K, M>* _pParent; // 在分裂節點后可能需要繼續向上插入，為實現簡單增加parent域size_t _size; // 節點中有效元素的個數BTreeNode(): _pParent(NULL), _size(0){for(size_t i = 0; i <= M; ++i)_pSub[i] = NULL;}
};

---

B樹的插入

下面拿一個 M=3 的 三叉B樹 來舉例子。（PS：三叉樹即每個節點至多 3 個孩子，2 個 key，key 的數量永遠比孩子少一個）

假設使用以下數據構建B樹 {63, 131, 85, 39, 148, 31, 111}（B樹從葉子節點的位置進行插入）：

首先依次插入前三個節點，當插入到第三個時，由于三叉樹的 key 只能有 2 個，所以此時會采取分裂的方法來維持樹的平衡。

B樹分裂的規則是：創建一個兄弟節點，拷貝右半區間的數據到兄弟節點，左半區間保留，中位數放到父親節點（如果沒有則創建新的根節點）。

B樹 與 AVL 的旋轉、紅黑樹的旋轉+變色不一樣，它使用了分裂的方法來維持樹的平衡，這樣的好處是既能做到平衡，也保證了非根節點至少有一半的空間利用率。

所以此時按照上面的規則進行分裂：

接著插入 39，148 ：

然后插入 31，開始分裂：

接著插入111，此時再次發生分裂：

此時可以看到，葉子節點已經分裂成了 4 個，并且根節點的 key 也達到了 3 個，不符合 B樹 的性質：每個根節點最多有 M 個孩子、M - 1 個key，因此繼續分裂：

此時，樹重新平衡。從上面可以看出來，本質上B樹的設計還是參考了二叉搜索樹。

---

B樹的遍歷

B樹的有序遍歷還是通過中序遍歷來完成，不過需要通過隊列或者遞歸遍歷完這個節點的所有的key。

void _InOrder(PNode pRoot)
{if(NULL == pRoot)return;for(size_t i = 0; i < pRoot->_size; ++i){_InOrder(pRoot->_pSub[i]);cout << pRoot->_keys[i] << " ";}_InOrder(pRoot->_pSub[pRoot->_size]);
}

B樹的性能

作為一個M路平衡搜索樹，B樹的搜索性能達到了 ${\log }_{M+1}N$ ~ ${\log }_{M/2}N$ 之間，查找到指定關鍵字的方法是：

• 在根結點所包含的關鍵字 K1、…、Kn 查找給定的關鍵字（可用順序查找或二分查找法），若找到等于給定值的關鍵字，則查找成功；
• 否則，一定可以確定要查找的關鍵字在 Ki 與 Ki+1之間，Pi 為指向子樹根節點的指針，此時取指針 Pi 所指的結點繼續查找，直至找到，或指針 Pi 為空 時查找失敗。

比起二叉平衡搜索樹，速度快了一大截，并且大大的減少了硬盤 IO 的次數，所以在文件系統以及數據庫索引等方面使用的都是這種數據結構。

---

B+樹

B+樹是B樹的變形，主要性質如下：

• 其定義基本與B樹相同
• 非葉子節點的 孩子 與 key 個數相同（簡化規則）
• 非葉子節點由葉子節點的最小值構成（充當索引，所以不可能在非葉子節點命中）
• 所有數據都出現在葉子節點，并且所有葉子節點都鏈接起來，同時是有序的。（方便遍歷）

---

B+樹的插入

這里為了方便，使用 三階B+樹 舉例子，這里還是使用同樣的數據。{63, 131, 85, 39, 148, 31, 111}

首先插入 63，并把 63 作為父節點的索引:

接著插入 131，85 :

當插入 39 時，發生分裂，分裂規則與之前略有區別。

B+樹的分裂規則：因為此時父節點存儲的是索引，所以此時只會將左半部分數據保留，右半部分數據放入新建的兄弟節點，并且會向上更新父節點的索引。

當插入 111 時，發生分裂：

---

B+樹的遍歷

從上面可以看出來，B+樹的主要特點其實就是更方便進行遍歷，因為其將所有數據存儲在葉子節點，所有非葉子節點就相當于一個索引。其所有葉子節點連接起來，像遍歷鏈表一樣遍歷B+樹。這樣的結構使得B+樹的查找相當于對關鍵字全集做一次二分查找。

所以通常文件的索引系統都會采用B+樹的結構。

---

B*樹

B*樹則又是對B+樹的變形，其性質如下：

• 其定義基本與B+樹相同
• 將非葉子節點也連接起來
• 分裂方式再次修改，保證每個節點中 key 的數量 [2/3 * M，M]（提高空間利用率，從1/2提升到了2/3）

---

B*樹的插入

B*樹再次修改了插入規則，規則修改為：

• 如果當前節點數據已滿而兄弟節點未滿，則將數據放入兄弟節點，而當兩個節點都滿了之后再進行分裂；
• 分裂時，在原節點與兄弟節點之間創建新節點，從兩個節點分別取出 1/3 的數據放入新創建的結點。

還是原來那些數據 {63, 131, 85, 39, 148, 31, 111} :

接下來插入 39：

插入 148、31：

此時插入111，發生分裂，從兩邊各取走 1/3 的數據：

從上面可以看出，B*樹的最大改進就是將B+樹的空間利用率從1/2提升到了2/3，并且對非葉子節點也進行了連接，查找更加便利。

---

總結