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

1.? 每個節點存儲多個元素 （但元素數量不能無限多，否則查找就退化成了節點內部的線性查找了）。

2.? 摒棄二叉樹結構，采用多叉樹 （由于節點內元素數量不能無限多，自然子樹的數量也就不會無限多了）。

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

?

【2-4樹】

?

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

1. 大小性質：每個結點最多4個子結點。

2. 深度性質：所有外部結點的深度相同。

?

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

?

?

【B~樹】

?

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

1)? 樹中每個結點至多有m個孩子；

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

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

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

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

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

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

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

?

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

(為了簡單，這里用少量數據構造一棵2-4樹的形式，其實實際應用中的B樹結點中關鍵字很多的)

?

B~樹的建立

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

關于B~樹以及后面B+樹的插入，刪除操作，在《 數據結構算法與應用-搜索樹 》中有詳細講解。

?

關于文件目錄索引的B~樹 磁盤 存儲結構及其查詢過程

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

?

首先，我們構造一個B樹結點的信息：

    class BTNode<E extends Comparable<E>>{

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

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

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

????? 現在我們模擬查找文件29的過程：

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

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

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

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

????? (5) 根據p2指針，我們定位到磁盤塊8，并將其中的信息導入內存。【磁盤IO操作3次】

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

?

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

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

?

?

【B+樹】

?

?

B+樹：是應文件系統所需而產生的一種B~樹的變形樹。 一棵m階的B+樹和m階的B-樹的差異在于：

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

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

?

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

?

下面我們用另外一個圖來看一下B+樹葉子節點和非終節點的特點：

?

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

?

關于FOXPRO索引文件的B+樹磁盤存儲結構及其查詢

B+樹在數據庫，文件系統的索引結構中是十分常用的。關于B+樹的磁盤存儲可以參見上面B~樹的情況，其一個結點用一個磁盤塊存儲。在這里我們對FOXPRO索引文件做一個簡單的介紹，讓大家對B+樹的磁盤存儲有一個大致的了解。

?

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

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

字節	????????????????????????? 內容
0-3	標識根結點所在塊號
4-7	保留
8-11	索引文件總塊數
12	索引文件的關鍵字長度
16	索引關鍵字表達式(以ASCII碼存放）

?

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

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

?

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

?

B+樹的優勢所在

?

為什么說B+樹比B~樹更適合實際應用中操作系統的文件索引和數據庫索引？

?

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

?

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

?

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

?

?

2、B+樹的查詢效率更加穩定。

?

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

?

?

?

?

【查找結構5】多路查找樹/B~樹/B+樹