在前面專題中講的BST、AVL、RBT都是典型的二叉查找樹結(jié)構(gòu)，其查找的時間復雜度與樹高相關(guān)。那么降低樹高自然對查找效率是有所幫助的。另外還有一個比較實際的問題：就是大量數(shù)據(jù)存儲中，實現(xiàn)查詢這樣一個實際背景下，平衡二叉樹由于樹深度過大而造成磁盤IO讀寫過于頻繁，進而導致效率低下。那么如何減少樹的深度（當然不能減少查詢數(shù)據(jù)量），一個基本的想法就是：

1. 每個節(jié)點存儲多個元素（但元素數(shù)量不能無限多，否則查找就退化成了節(jié)點內(nèi)部的線性查找了）。

2. 摒棄二叉樹結(jié)構(gòu)，采用多叉樹（由于節(jié)點內(nèi)元素數(shù)量不能無限多，自然子樹的數(shù)量也就不會無限多了）。

這樣我們就提出來了一個新的查找樹結(jié)構(gòu) ——多路查找樹。根據(jù)AVL給我們的啟發(fā)，一顆平衡多路查找樹(B~樹)自然可以使得數(shù)據(jù)的查找效率保證在O(logN)這樣的對數(shù)級別上。

【2-4樹】

(2,4)樹是一棵典型的平衡多路查找樹。性質(zhì)如下：

1. 大小性質(zhì)：每個結(jié)點最多4個子結(jié)點。

2. 深度性質(zhì)：所有外部結(jié)點的深度相同。

(2,4)其實是一棵迷你型的B樹，其主要應用并不是為了將大數(shù)據(jù)量存儲在外存上，而是通過減少樹高來降低二叉查找樹的查找代價。在介紹下面的B~樹/B+樹之前，請大家首先了解一下《外部存儲器—磁盤》。

【B~樹】

B~樹，又叫平衡多路查找樹。一棵m階的B~樹 (m叉樹)的特性如下：

1) 樹中每個結(jié)點至多有m個孩子；

2) 除根結(jié)點和葉子結(jié)點外，其它每個結(jié)點至少有[m/2]個孩子；

3) 若根結(jié)點不是葉子結(jié)點，則至少有2個孩子；

4) 所有葉子結(jié)點都出現(xiàn)在同一層，葉子結(jié)點不包含任何關(guān)鍵字信息(可以看做是外部接點或查詢失敗的接點，實際上這些結(jié)點不存在，指向這些結(jié)點的指針都為null)；

5) 每個非終端結(jié)點中包含有n個關(guān)鍵字信息： (n，A0，K1，A1，K2，A2，......，Kn，An)。其中，

a) Ki (i=1...n)為關(guān)鍵字，且關(guān)鍵字按順序排序Ki < K(i-1)。

b) Ai為指向子樹根的接點，且指針A(i-1)指向子樹種所有結(jié)點的關(guān)鍵字均小于Ki，但都大于K(i-1)。

c) 關(guān)鍵字的個數(shù)n必須滿足： [m/2]-1 <= n <= m-1

例如：下面就是一棵3階B~樹

 

 

B~樹的建立

由于B~樹結(jié)點中的關(guān)鍵字個數(shù)必須>=[m/2]-1。因此和平衡二叉樹不同，每一次插入一個關(guān)鍵字并不是在樹中添加一個結(jié)點，而是首先在最低層的某個非終端結(jié)點中添加一個關(guān)鍵字，若該結(jié)點的關(guān)鍵字個數(shù)不超過m-1，則插入完成。否則，要產(chǎn)生結(jié)點的"分裂"。

關(guān)于B~樹以及后面B+樹的插入，刪除操作，在《數(shù)據(jù)結(jié)構(gòu)算法與應用-搜索樹》中有詳細講解。

關(guān)于文件目錄索引的B~樹磁盤存儲結(jié)構(gòu)及其查詢過程

既然我們說過B~樹相比平衡二叉樹的一個巨大的特點就是：海量數(shù)據(jù)存儲時B~樹利用磁盤存儲的效率會高很多。那么我們現(xiàn)在就來簡單的看看操作系統(tǒng)中文件目錄的B~樹結(jié)構(gòu)是怎樣的(這里只介紹簡單的原理，至于想Windows,Linux的文件系統(tǒng)使用的是B+樹結(jié)構(gòu)，而且技術(shù)遠遠比這里介紹的復雜)。

首先，我們構(gòu)造一個B樹結(jié)點的信息：

class BTNode<E extends Comparable<E>>{

         // 結(jié)點中文件個數(shù)
         int  filenum;  
         //子樹的根結(jié)點指針向量
         BTNode[]  ptr=new BTNode(filenum+1);  
         //文件名向量 
         E[] filename=new E(filenum); 
         // 指向磁盤中文件存儲地址向量
         FileHardAddress[]   recptr=new FileHardAddress(filenum);
         
}

上面的圖中比如根結(jié)點，其中17表示一個磁盤文件的文件名；小紅方塊表示這個17文件的內(nèi)容在硬盤中的存儲位置；p1表示指向17左子樹的指針。

我們現(xiàn)在把整棵樹構(gòu)造在磁盤中，假如每個盤塊可以正好存放一個B~樹的結(jié)點（正好存放2個文件名）。那么一個BTNode結(jié)點就代表一個盤塊，而子樹指針就是存放另外一個盤塊（詳細見《外部存儲器—磁盤》）的地址。

現(xiàn)在我們模擬查找文件29的過程：

(1) 根據(jù)根結(jié)點指針找到文件目錄的根磁盤塊1，將其中的信息導入內(nèi)存?！敬疟PIO操作1次】

(2) 此時內(nèi)存中有兩個文件名17，35和三個存儲其他磁盤頁面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)17<29<35，因此我們找到指針p2。

(3) 根據(jù)p2指針，我們定位到磁盤塊3，并將其中的信息導入內(nèi)存?！敬疟PIO操作2次】

(4) 此時內(nèi)存中有兩個文件名26，30和三個存儲其他磁盤頁面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)26<29<30，因此我們找到指針p2。

(5) 根據(jù)p2指針，我們定位到磁盤塊8，并將其中的信息導入內(nèi)存?！敬疟PIO操作3次】

(6) 此時內(nèi)存中有兩個文件名28，29。根據(jù)算法我們查找到文件29，并定位了該文件內(nèi)存的磁盤地址。

分析一下上面的過程，我們發(fā)現(xiàn)需要3次磁盤IO操作和3次內(nèi)存查找操作。關(guān)于內(nèi)存中的文件名查找，由于是一個有序表結(jié)構(gòu)，可以利用折半查找提高效率。至于3次磁盤IO操作時影響整個B~樹查找效率的決定因素。

當然，如果我們使用平衡二叉樹的磁盤存儲結(jié)構(gòu)來進行查找，磁盤IO操作最少4次，最多5次。而且文件越多，B~樹比平衡二叉樹所用的磁盤IO操作次數(shù)將越少，效率也越高。

【B+樹】

B+樹：是應文件系統(tǒng)所需而產(chǎn)生的一種B~樹的變形樹。一棵m階的B+樹和m階的B-樹的差異在于：

1) 有n棵子樹的結(jié)點中含有n個關(guān)鍵字； (B~樹是n棵子樹有n+1個關(guān)鍵字)
2) 所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大的順序鏈接。(B~樹的葉子節(jié)點并沒有包括全部需要查找的信息)

3) 所有的非終端結(jié)點可以看成是索引部分，結(jié)點中僅含有其子樹根結(jié)點中最大（或最?。╆P(guān)鍵字。(B~樹的非終節(jié)點也包含需要查找的有效信息)

 

 

 

 

上面這個圖有一個很重要的性質(zhì)：B+樹的葉子結(jié)點包含了所有待查詢關(guān)鍵字，而非終節(jié)點只是作為葉子結(jié)點中最大(最小)關(guān)鍵字的索引。因此B+樹的非終結(jié)點沒有文件內(nèi)容所在物理存儲的地址，而B~樹所有結(jié)點均有文件內(nèi)容所在的磁盤物理地址（B~樹結(jié)構(gòu)圖中結(jié)點內(nèi)部的小紅方塊）。這個特點是B+樹的一個重要優(yōu)勢所在。這一點我們在下面談及。

關(guān)于FOXPRO索引文件的B+樹磁盤存儲結(jié)構(gòu)及其查詢

B+樹在數(shù)據(jù)庫，文件系統(tǒng)的索引結(jié)構(gòu)中是十分常用的。關(guān)于B+樹的磁盤存儲可以參見上面B~樹的情況，其一個結(jié)點用一個磁盤塊存儲。在這里我們對FOXPRO索引文件做一個簡單的介紹，讓大家對B+樹的磁盤存儲有一個大致的了解。

FOXPRO的索引文件（后綴IDX）由索引文件頭和索引文件體組成。

文件頭占一個塊,相對于索引文件的物理零塊號,它描述索引文件的組織信息,包括索引樹的根結(jié)點位置,索引關(guān)鍵字表達式及索引關(guān)鍵字長度.其有用字節(jié)的含義如下表：

索引文件體從索引文件的相對物理塊號為1的塊開始,文件體的每塊也就是索引樹的一個結(jié)點。其中重要的是索引項。索引項=關(guān)鍵字+指針域(4字節(jié))。這就是我們上面常說的B+樹結(jié)點中的兩個重要的信息：待查詢關(guān)鍵字和指向另一個結(jié)點的指針。文件體每塊含義如下表：

B+樹的查找與B~樹類似。但通常B+樹有兩個頭指針，一個指向根結(jié)點。另一個指向關(guān)鍵字最小的葉子節(jié)點。此外，所有葉子結(jié)點也按照大小順序鏈接。因此，B+樹有兩種查找算法：一種從根結(jié)點出發(fā)，一種從葉子結(jié)點出發(fā)的順序查找。

B+樹的優(yōu)勢所在

為什么說B+樹比B~樹更適合實際應用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫索引？

1、B+樹的磁盤讀寫代價更低

我們都知道磁盤時可以塊存儲的，也就是同一個磁道上同一盤塊中的所有數(shù)據(jù)都可以一次全部讀取(詳見《外部存儲器—磁盤》)。而B+樹的內(nèi)部結(jié)點并沒有指向關(guān)鍵字具體信息的指針(比如文件內(nèi)容的具體地址，比如說不包含B~樹結(jié)點中的FileHardAddress[filenum]部分）。因此其內(nèi)部結(jié)點相對B~樹更小。如果把所有同一內(nèi)部結(jié)點的關(guān)鍵字存放在同一盤塊中，那么盤塊所能容納的關(guān)鍵字數(shù)量也越多。這樣，一次性讀入內(nèi)存中的需要查找的關(guān)鍵字也就越多。相對來說IO讀寫次數(shù)也就降低了。

舉個例子，假設磁盤中的一個盤塊容納16bytes，而一個關(guān)鍵字2bytes，一個關(guān)鍵字具體信息指針2bytes。一棵9階B~樹(一個結(jié)點最多8個關(guān)鍵字)的內(nèi)部結(jié)點需要2個盤快。而B+樹內(nèi)部結(jié)點只需要1個盤快。當需要把內(nèi)部結(jié)點讀入內(nèi)存中的時候，B~樹就比B+數(shù)多一次盤塊查找時間(在磁盤中就是盤片旋轉(zhuǎn)的時間)。

2、B+樹的查詢效率更加穩(wěn)定。

由于非終結(jié)點并不是最終指向文件內(nèi)容的結(jié)點，而只是葉子結(jié)點中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點到葉子結(jié)點的路。所有關(guān)鍵字查詢的路徑長度相同，導致每一個數(shù)據(jù)的查詢效率相當。