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

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

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

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

【2-4樹(shù)】

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

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

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

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

【B~樹(shù)】

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

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

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

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

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

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

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

例如：下面就是一棵3階B~樹(shù)

 

 

B~樹(shù)的建立

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

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

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

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

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

class BTNode<E extends Comparable<E>>{

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

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

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

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

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

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

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

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

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

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

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

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

【B+樹(shù)】

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

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

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

 

 

 

 

上面這個(gè)圖有一個(gè)很重要的性質(zhì)：B+樹(shù)的葉子結(jié)點(diǎn)包含了所有待查詢(xún)關(guān)鍵字，而非終節(jié)點(diǎn)只是作為葉子結(jié)點(diǎn)中最大(最小)關(guān)鍵字的索引。因此B+樹(shù)的非終結(jié)點(diǎn)沒(méi)有文件內(nèi)容所在物理存儲(chǔ)的地址，而B(niǎo)~樹(shù)所有結(jié)點(diǎn)均有文件內(nèi)容所在的磁盤(pán)物理地址（B~樹(shù)結(jié)構(gòu)圖中結(jié)點(diǎn)內(nèi)部的小紅方塊）。這個(gè)特點(diǎn)是B+樹(shù)的一個(gè)重要優(yōu)勢(shì)所在。這一點(diǎn)我們?cè)谙旅嬲劶啊?/P>

關(guān)于FOXPRO索引文件的B+樹(shù)磁盤(pán)存儲(chǔ)結(jié)構(gòu)及其查詢(xún)

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

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

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

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

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

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

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

1、B+樹(shù)的磁盤(pán)讀寫(xiě)代價(jià)更低

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

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

2、B+樹(shù)的查詢(xún)效率更加穩(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)鍵字查詢(xún)的路徑長(zhǎng)度相同，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢(xún)效率相當(dāng)。