在前面我們曾經寫過一個BSTree類，這個類大致上能滿足我們的要求。而為了在不同的輸入情況下，使得樹的高度盡可能的小，平衡樹的概念被提出來了，例如前面的AVLTree類。所謂的平衡，現在更多意義上是指和完全m叉樹高度的比值是小于某個常數的樹，也就是高度≤klogmn的樹，k為一個定常數。注意到AVL樹的定義實際上太苛刻，就很容易理解為什么要放寬要求。而實際能應用的平衡樹，都是為了滿足這個要求而自己定一套規則，比如B－樹，這個后面會講到。

有些字典會提供一個目錄，大部分情況是這樣的A……xx；B……xx；……。這樣就能迅速翻到開頭字母對應的頁數（實際上也知道了開頭字母結束的地方），并且每個頁的左右上角的單詞也說明了本頁的單詞范圍（可以判斷所查單詞在不在此頁）。這些就是索引。

使用索引能夠快速的定位查找范圍，從我們查字典的經驗看來，這也應該是能提高查找效率的方法。注意到目錄的作用，它使得我們所需的字典空間分布，在一頁（或者幾頁）的空間上迅速的被我們得到——類比來看，如果數據太多以至內存裝不下，我們也可以弄個“目錄”，使得可以將數據分塊的讀入內存查找。

當數據膨脹到一個可怕的程度時，連索引都不能被全部裝入內存——見過印刷版的EI檢索都有這個感覺，光一個檢索目錄都比我們用的字典厚。我們的辦法就是索引再索引，顯而易見的，每個索引塊都應該盡可能的大，以幫助我們獲得盡可能多的信息，而避免再次的查索引（此時一般都會涉及外存的存取）。AVL樹此時便力不從心了，我們需要一種新的結構。

相信每個學到這里的人都對B－樹的定義深惡痛絕，這個的責任應該由寫書的人來負，雖然定義、概念是人認知的重要工具和途徑，但在這里是適得其反的。原因就是B－樹根本不存在概念意義上的“概念”，它只是一個描述型的“概念”，是B－樹能夠運行從而表現出來的一種現象。不管怎么說，先看一下現有的書上的定義（省略了“或者為空樹”這句話）：

嚴蔚敏、吳偉民《數據結構（C語言版）》

1.         每個節點至多有m棵子樹

2.         若根不是葉子節點，至少有兩棵子樹

3.         除根以外的所有非終端節點至少有ém/2ù棵子樹

4.         所有非終端節點包含下列信息數據（n，A0，K1，A1，K2，A2……，Kn，An），其中，Ki為關鍵字，且Ki<Ki+1（i＝1，2，……，n－1）；Ai（i＝0，……，n）為指向子樹根節點的指針，且指針Ai-1所指子樹中所有節點的關鍵字均小于Ki（i＝1，……，n），An所指子樹中所有的節點的關鍵字均大于Kn，n（ém/2ù-1￡ n ￡ m-1）為關鍵字的個數（或n+1為子樹個數）。

5.         所有的葉子節點都出現在同一層次上，并不帶信息（可以看作是外部節點或查找失敗的節點，實際上這些節點不存在，指向這些節點的指針為空）。

殷人昆等《數據結構（用面向對象方法與C++描述）》

1.         m路搜索樹（實際上是上面第1、4條的內容）

2.         根節點至少有兩個子女

3.         除根節點以外的所有節點（不包括失敗節點）至少有ém/2ù個子女

4.         所有的失敗節點都位于同一層。事實上，這些節點都是作為外部節點存在，不是樹上的節點。

非常莫名其妙的定義——憑什么根至少有兩個子女，而其他的至少ém/2ù個子女？跟AVL樹的定義比較一下就能看出這個定義的不合理處——AVL樹只是給出了平衡的定義“左右子樹高度差不超過1”，至于什么平衡因子、旋轉，根本就沒有提及，那只是為了保證平衡的手段。顯然，現在的B－樹的定義，把為了保證平衡而采取措施的結果包括在定義之中了，而這必將導致人的認知上的迷惑，因此這樣的定義是不合格的。或許，一個不和現在定義矛盾的合理的定義應該是這樣：采用如下辦法達到“平衡”的m路搜索樹……，當然，我們首先要解決什么叫“平衡”，而這個直覺上的定義前面已經提到了。

接下來，讓我們看看保持平衡的“如下辦法”是什么。回憶一下AVL樹，那時的旋轉確實是很精妙的方法——保持中序有序的情況下改變子樹高度差，我也耗費了不少腦細胞把AVL樹的講解從書上的莫名其妙變成了按部就班，這是本人到目前為止最為得意的一件事情，到大家能看到這篇文字的時候，應該也能看見我寫的AVL樹的講解了。

兩個叉的AVL樹能旋轉，m個叉的樹怎么轉？看來得換個思路，前人已經為我們做到了，就是節點的分裂和合并。

Ø         分裂

節點裝不下的時候就分裂，也就是說對于一個節點，當第m個元素進來的時候，就要分裂。怎么分裂？以中間元素為軸，左右兩部分各形成一個節點，作為中間元素的左右孩子——這里還是借用了二叉樹的概念，而事實上，m叉搜索樹就是多個二叉搜索樹拼合的產物——這樣還是中序有序的（或許不該說“中序”，大家結合二叉樹自己理解吧），中間元素帶著這兩個孩子插入到原來節點的父節點，當然，父節點滿的時候同樣要分裂，這樣一層層直到根節點（或者不用分裂）。

縱觀分裂的過程，我們才能明白前面的定義是怎么回事。如果采用如上的分裂方法，對于根節點來說，要么沒有子女，要么一分裂就兩個子女。而對于非根節點，只有當節點滿的時候才會分裂，那自然最少有ém/2ù個子女。

而“所有的失敗節點都位于同一層”是B－樹的“平衡準則”，很容易就能看出這樣的樹是“平衡”的。

所以，關于B－樹的定義實際上是B－樹維持平衡的外在表現，它不應該作為B－樹的定義，而只能是一種描述。

Ø         合并

和二叉搜索樹一樣，刪除都歸結成在葉子節點的刪除，如果不在葉子節點，就拿葉子節點中的覆蓋掉，轉化成在葉子節點的刪除。同樣的，當不平衡出現時（即不滿足上面B－樹的描述），需要平衡化。

我們看到，父節點中的元素和左右兩個孩子原來可能是一個節點的，或者可以說他們可以合并成一個節點。這樣一來，如果他們的元素總和大于m－1，那么就從多的向少的撥一個元素——想想電視里老和尚手里的念珠，元素的移動過程是這樣的：元素多的節點——父節點（手里的珠子）——元素少的節點。如果他們的元素總和小于等于m－1，那么就把他們合并成一個節點，這樣一來，父節點就會少一個元素，如果也出現了不平衡，也同樣處理。

觀看分裂合并的過程，就會發現插入刪除的起點都在葉子節點，出現不平衡后，無論分裂還是合并，都會把多了（或者少了）一個元素的變化傳遞到父節點，從而導致對父節點的再度平衡化。和AVL樹的調整簡直是如出一轍，不同的是，AVL樹不可能分裂合并，因此采取的是旋轉的辦法；或者可以說B－樹不能旋轉，因此采取了分裂合并。而兩種調整方法都是在保持有序的情況下，使樹高（差）發生了變化。

當樹的叉多起來的時候，操作起來都會覺得不便，因此B－樹更應該是為了減少內外存交換開銷而提出來的，和外排一樣，對一般的應用意義不大，不做系統級別的應用（或者是為了考試）很少會用到，就不再具體講解了。

而如果僅是在內存中，叉的數目少一點會比較好，比如3叉（因為這樣的樹每個節點有2或3個叉，又叫2－3樹），而實際上，AVL樹（或者紅黑樹）已經做得很好了，沒必要費心在多叉搜索樹上。

想想人們還真煩，B－樹都有人認為是Binary樹了，又來一個B＋樹，看來老外還真是該打，Binary和Balance縮寫也不多保留幾個字母，都是B。

B＋樹更是為了外存而提出來的，同樣的，一般用途不大，一般人不必費心了（考試的例外）。注意的是和B－樹的幾點差別：B＋樹的非葉子節點都是索引，因此當刪除關鍵碼的時候，有些情況不必改動索引，查到了關鍵字也要一直走到葉子節點；另外所有的葉子節點都是鏈接在一起的，從頭到尾可以順序遍歷——和線索二叉樹很像不是嗎？

嚴版的和殷版的在B＋樹的定義（更準確的說是描述）上有一個很大的分歧（節點中幾個元素幾個子樹），從教學的目的上，我同意殷版的描述，因為這樣的描述能更直接的表達B＋樹是如何從B－樹演化來的，嚴版的引入了額外的區分，分散了讀者的注意力。

我更覺得哈希表是因為目前的儲存結構而誕生的。想想我們的儲存器（RAM），每個單元對應一個地址，對于數組來說，當知道首地址后，可以馬上計算出第N個元素的地址，因此可以馬上讀取。反過來說，卻不能由內容來確定元素的地址，想知道含某個內容的單元的地址，就必須挨個查看，或者在有序的情況下折半查找。

而當我們的儲存器能夠支持按內容存取的話，那我們前面介紹的一切查找方法都會變得黯淡無光——想找15，馬上就能定位到15的位置，這樣O(1)的方法簡直是人們夢寐以求的。不知是幸運（前面查找的方法還是大有用武之地）還是不幸（直接的O(1)查找不可能容易的實現），我們想要的那種類型的儲存器（相聯存儲器）貴的要命（也可能容量根本做不大）。

既然硬件不支持，就從軟件下手吧，前面費了點口舌，是為了使大家明白現有的方法是建立在現有的結構上的，而當現有體系發生改變的時候，方法也會跟著改變。

顯然，只要我們能在內容和序號之間建立一種函數關系，在現有儲存結構上就能實現按內容存取了——內容→函數變換→序號。

實際上，任何可列的內容都是可以和整數一一對應的（我們總能找到這樣的法則），但是，一一對應的代價很可能是整數的范圍很廣，結果使得空間的浪費很大。打個比方，一張1901～2000年事件索引表，只需要一個100大小的數組，0元素代表1901，99元素代表2000——這里也回答了很多人疑惑的問題，2000年究竟是不是21世紀，這么一對照就會發現這是個歷史遺留問題，公元元年是公元1年而不是公元0年才會導致這樣的問題，歷法幾千年來修訂了好幾回，我們也不要對這個問題太較真了，一句話，隨大流。然而我們如果做一個人類歷史的索引表，上下五千年（把古代人算上就是多少萬年了），但卻不是每年都有事發生（應該說是值得我們注意的事），更有甚者是確切的年份都不知道，顯然前面的做法就不太合理了，絕大多數空間都是空閑的。

因此，實際上采用的函數變換都是帶有壓縮性質的，即輸出的值域都是有限的一個范圍，典型的就是0～表長。就像我們的日常經驗一樣，一壓縮，就會有些元素被擠到一起，“你我不分”了。因此，還必須有合理處理“沖突”的辦法。函數變換加上“沖突”處理方法，就構成了散列這種查找方法。

具體的散列函數和沖突處理，請閱讀教科書，我不再詳細說明了。

這其實都是建立在散列的思想上的，在他們身上，很容易就能發現鏈散列的影子，而Trie樹更像是靜態的基數排序。Trie樹用來組織內存中的數據也是很好用的，并非是只適用于外存。那么一本厚書也僅僅是一兩頁，我這幾十頁的有這么一段也差不多了，^_^。具體請閱讀教科書，一般讀者可跳過。