多路查找樹（2-3 樹、2-3-4 樹、B 樹、B+ 樹）
本文參考自《大話數據結構》
電腦中數據的存儲
一般而言，我們都是在記憶體中處理數據，但假如我們要操作的數據集非常大，記憶體無法處理了，在這種情況下對數據的處理需要不斷地從硬碟等存儲設備中調入或調出記憶體頁面。
對外存設備的讀寫，效率並不樂觀。為了降低對外存設備的訪問次數，我們需要新的數據結構來處理這個問題。之前學習過的樹，一個結點可以有多個孩子，但它自身只能存儲一個元素。二叉樹限制更多，只有兩個孩子結點。在元素非常多時，要麼樹的度非常大（結點擁有子樹的個數的最大值），要麼樹的高度非常大，如果我們要查找某一元素，必須多次訪問外存設備，這迫使我們要打破每一個結點只能存儲一個元素的限制，引入多路查找樹的概念。
多路查找樹，其每一個結點的孩子數可以多於兩個，且一個結點可以存儲多個元素。由於它是查找樹，所有元素之間存在某種特定的排序關係。
2-3 樹和 2-3-4 樹
2-3 樹是擁有以下性質的多路查找樹：
-
每一個結點都具有兩個孩子（稱為 2 結點）獲三個孩子（稱為 3 孩子）
-
一個 2 結點包含一個元素和兩個孩子（或沒有孩子），左子樹包含的元素小於該元素，右子樹包含的元素大於該元素
-
一個 3 結點包含一大一小兩個元素和三個孩子（或沒有孩子），左子樹包含的元素小於較小元素，右子樹包含的元素大於較大元素，中間子樹包含介於兩個元素之間的元素
-
2-3 樹中所有的葉子結點都在同一層次上
對於 2-3 樹，查找某一元素的方法與二叉排序樹一樣。要判斷一個元素是否存在，我們先將待查找元素和根節點比較，如果它和其中任意一個相等，那查找命中；否則根據比較的結果來選擇查找的方向。
要對 2-3 樹插入元素，如果是一顆空樹，直接創建一個 2 結點即可，如果不是空樹，則要考慮以下情況：
-
插入結點到一個 2 結點，可直接將 2 結點轉換為 3 結點
-
插入結點到一個 3 結點，其父結點為 2 結點
如果命中查找結束於 3 結點，先臨時將其成為 4 結點，把待插入元素添加到其中，然後將 4 結點轉化為 3 個 2 結點，中間的結點成為左右結點的父結點，並與父結點為合併。
-
插入結點到一個 3 結點，其父結點為 3 結點
插入元素後一直向上分解臨時的 4 節點，直到遇到 2 節點的父節點變成 3 節點不再分解為止。如果達到樹根節點還是 4 節點，則分解根節點，此時樹高加一（只有分解根節點才會增加樹高）。
對於 2-3 樹的刪除，如果對前面插入的理解到位的話，就不是難事了。相比於插入，刪除的情況較多，如果逐一介紹就太浪費時間了，總的來說它是有規律的。
2-3-4 樹其實就是 2-3 樹的概念擴展，它多了一個 4 結點。一個 4 結點包含小中大三個元素和四個孩子（或沒有孩子），左子樹包含小於最小元素的元素；第二子樹包含大於最小元素，小於第二元素的元素；第三子樹包含大於第二元素，小於最大元素的元素；右子樹包含大於最大元素的元素。
B 樹和 B+ 樹
B 樹是一種平衡的多路查找樹，2-3 樹和 2-3-4 樹都是 B 樹的特例，結點所擁有的最大孩子樹稱為 B 樹的階，因此，2-3 樹是 3 階 B 樹，2-3-4 樹是 4 階 B 樹。
一個 m 階的 B 樹具有如下屬性：
- 如果根結點不是葉結點，則至少有兩顆子樹
- 每一個非根的分支結點都有 k-1 個元素和 k 個孩子
- 所有葉子結點都處於同一層次
- 值位於 k-1 和 k 之間的子結點，都位於 k-1 和 k 對應的 value 之間
B 樹的插入和刪除和 2-3 樹或 2-3-4 樹是類似的，只不過階數可能會很大而已。B 樹可以幫助我們減少記憶體與外存之間數據的頻繁交換，假設一顆 B 樹的階是 1001，高度為 2，它可以存儲超過 10 億個關鍵字。我們只要讓根結點持久保留在記憶體中，那麼尋找一個關鍵字至多只需要兩次硬碟的讀取。而如果使用二叉樹，那就不得了了，光是樹的高度就不知道比使用 B 大到哪裡去，對硬碟的讀取次數自然也多得多。
B 樹還是有缺陷的，如果我們要遍歷一顆 B 樹，必須往返於每個結點之間，也就意味著得多次訪問硬碟，有沒有可能讓遍歷時每個元素只訪問一次呢？我們在原有的 B 樹結構基礎上，加上新的元素組織形式，這就是 B+ 樹。
B+ 樹與 B 樹的差異在於：
- B+ 樹的分支結點不保存關鍵字，只進行數據索引，結點中僅含有其子樹中的最大（或最小）關鍵字
- B+ 樹所有的葉子結點包含全部關鍵字資訊，及指向含這些關鍵字記錄的指針，葉子結點本身依關鍵字的大小從小到大順序鏈接
B+ 所有關鍵字數據地址都存在葉子節點上，所以每次查找的次數都相同，查詢效率也比 B 樹穩定。B+ 樹也結點遍歷速度更快，因為只需要從最左側的葉子結點出發，一直沿著指向下一葉子結點的指針遍歷即可。另外，B+ 樹天然具備排序功能，因此特別適合帶有範圍的查找。
