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

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

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

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

?

【2-4樹】

?

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

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

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

?

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

?

?

【B~樹】

?

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

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

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

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

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

5)? 每個非終端結(jié)點(diǎn)中包含有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為指向子樹根的接點(diǎn)，且指針A(i-1)指向子樹種所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki，但都大于K(i-1)。

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

?

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

(為了簡單，這里用少量數(shù)據(jù)構(gòu)造一棵2-4樹的形式，其實(shí)實(shí)際應(yīng)用中的B樹結(jié)點(diǎn)中關(guān)鍵字很多的)

?

B~樹的建立

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

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

?

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

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

?

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

    class BTNode<E extends Comparable<E>>{

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

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

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

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

????? (1) 根據(jù)根結(jié)點(diǎn)指針找到文件目錄的根磁盤塊1，將其中的信息導(dǎo)入內(nèi)存。【磁盤IO操作1次】

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

????? (3) 根據(jù)p2指針，我們定位到磁盤塊3，并將其中的信息導(dǎo)入內(nèi)存。【磁盤IO操作2次】

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

????? (5) 根據(jù)p2指針，我們定位到磁盤塊8，并將其中的信息導(dǎo)入內(nèi)存。【磁盤IO操作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~樹查找效率的決定因素。

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

?

?

【B+樹】

?

?

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

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

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

?

例如：下面就是一棵3階B+樹。我們可以和B~樹做一個明顯的對比。

?

下面我們用另外一個圖來看一下B+樹葉子節(jié)點(diǎn)和非終節(jié)點(diǎn)的特點(diǎn)：

?

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

?

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

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

?

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

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

字節(jié)	????????????????????????? 內(nèi)容
0-3	標(biāo)識根結(jié)點(diǎn)所在塊號
4-7	保留
8-11	索引文件總塊數(shù)
12	索引文件的關(guān)鍵字長度
16	索引關(guān)鍵字表達(dá)式(以ASCII碼存放）

?

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

字節(jié)	??????????????? 內(nèi)容
0	塊屬性標(biāo)記.00H:非葉結(jié)點(diǎn)和根結(jié)點(diǎn).01H:根結(jié)點(diǎn),02H:葉結(jié)點(diǎn).03H:既是根結(jié)點(diǎn)又是葉結(jié)點(diǎn).
1	00H
2,3	塊內(nèi)索引項(xiàng)總數(shù) (多個索引項(xiàng))
4-7	同一層前繼結(jié)點(diǎn)塊號或4個FFFF值
8-11	同一層后繼結(jié)點(diǎn)塊號或4個FFFF值
12-	非遞減順序存放的索引項(xiàng)內(nèi)容

?

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

?

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

?

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

?

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

?

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

?

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

?

?

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

?

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

?

?

?

?

【查找結(jié)構(gòu)5】多路查找樹/B~樹/B+樹