郝愛語

摘 要：在基于地理位置的搜索中，對海量文檔某些屬性值的范圍進行查詢是比較迫切的需求，B Tree是解決這類問題的一個主要辦法，文章給出了B Tree文件系統(tǒng)的設(shè)計方案，闡述了B樹結(jié)構(gòu)及其相應(yīng)操作，并提出由B樹提升至B*樹的設(shè)想。

關(guān)鍵詞：B樹 B*樹 磁盤節(jié)點

一、提出問題

根據(jù)搜索系統(tǒng)的實際需要，查詢操作的基本需求明細見表1所示。

表1 查詢操作需求明細

二、B樹概述

1. B樹定義

B樹，即二叉搜索樹，是一種平衡樹，其定義是：所有非葉子結(jié)點至多擁有兩個兒子（Left和Right）；所有結(jié)點存儲一個關(guān)鍵字；非葉子結(jié)點的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹，如圖1所示。

B樹滿足基本的平衡樹的時間和空間復(fù)雜度，最初的B樹會在節(jié)點上面保存實際數(shù)據(jù)，改進后的B+樹只在葉子節(jié)點保存實際數(shù)據(jù)（或者指針），B樹滿足下面的一些基本特性。

1） 節(jié)點用指針連接

2） 有頭節(jié)點、中間節(jié)點和葉子節(jié)點之分

3） 每個葉子節(jié)點的深度都是一樣的

4） 只有葉子節(jié)點存放數(shù)據(jù)（或者數(shù)據(jù)指針）

5） 每個節(jié)點的孩子個數(shù)最大為N，最小為N/2

6） 頭節(jié)點的孩子個數(shù)可以少于N/2

7） 查找的時候，根據(jù)key值往下遍歷

圖1 B樹及其節(jié)點結(jié)構(gòu)這里需要注意：在葉子節(jié)點上面，每個key都對應(yīng)一個value，這個value的值是值得考慮的，正常來說，這個value都是一個指針，指向具體數(shù)據(jù)的位置，但是當(dāng)value的size不大的時候，可以把value變成任何值。

2. B樹節(jié)點結(jié)構(gòu)

一般的說，B樹有3種類型的節(jié)點，即：頭節(jié)點、中間節(jié)點和葉子節(jié)點，其中，頭節(jié)點和中間節(jié)點的差異很小，可以放到一起考慮。首先，所有的節(jié)點都包含了如下的數(shù)據(jù)元素：

1） 節(jié)點ID

2） 節(jié)點包含的Key值數(shù)組

3） 節(jié)點的層次

4） 節(jié)點的類型

中間節(jié)點還包含了如下的數(shù)據(jù)：節(jié)點的孩子ID數(shù)組

葉子節(jié)點還包含了如下的數(shù)據(jù)：節(jié)點Key數(shù)組對應(yīng)的實際數(shù)值數(shù)組

內(nèi)存中的葉子節(jié)點還包含了dirty屬性，標(biāo)明節(jié)點是否被修改了，而緩沖中的節(jié)點還會有對應(yīng)的權(quán)重。

3. B樹基本信息

B樹基本信息保存了有關(guān)B樹的所有配置信息和每個節(jié)點的物理位置，B樹的配置信息包含有：

1） 中間節(jié)點的最大孩子數(shù)

2） 中間節(jié)點的最小孩子數(shù)（或許這里會用分裂規(guī)則替代，或者直接使用1-2分裂，忽略第一個參數(shù)）

3） Key值類型；這個參數(shù)是否需要還需要考慮

4） 每個節(jié)點的物理位置，每個節(jié)點的物理位置是一個3元組，即：

4. B樹的一般原則

B樹在結(jié)構(gòu)上沒有對其每個節(jié)點包含的元素個數(shù)以及樹的高度進行任何限制，實際應(yīng)用中，一般應(yīng)該滿足如下原則：

1） 每個節(jié)點包含的Key值最大個數(shù) >= 200

2） B樹的高度 <= 4

5. B樹的搜索

B樹的搜索，要從根結(jié)點開始，如果查詢的關(guān)鍵字與結(jié)點的關(guān)鍵字相等，則搜索成果；否則，如果查詢關(guān)鍵字比結(jié)點關(guān)鍵字小，就進入左孩子結(jié)點；如果比結(jié)點關(guān)鍵字大，就進入右孩子結(jié)點；如果左孩子或右孩子結(jié)點的指針為空，則顯示提示消息：“找不到相應(yīng)的關(guān)鍵字”；

如果B樹的所有非葉子結(jié)點的左右子樹的結(jié)點數(shù)目均保持平衡，那么B樹的搜索性能逼近二分查找。相比連續(xù)內(nèi)存空間的二分查找，B樹的優(yōu)點是：改變B樹結(jié)構(gòu)（插入與刪除結(jié)點）不需要移動大段的內(nèi)存數(shù)據(jù)，甚至通常是常數(shù)開銷，如圖2和圖3所示。

圖2 插入結(jié)點結(jié)構(gòu)（1）

圖3 插入節(jié)點結(jié)構(gòu)（2）但是B樹在經(jīng)過多次插入與刪除后，有可能導(dǎo)致不同的結(jié)構(gòu)：

圖4 插入或刪除操作前結(jié)構(gòu)圖5所示的結(jié)構(gòu)也是一個B樹，但它的搜索性能已經(jīng)是線性的了，同樣的關(guān)鍵字集合有可能導(dǎo)致不同的樹結(jié)構(gòu)索引。所以在使用B樹的時候，還需要考慮盡可能讓B樹保持圖4的結(jié)構(gòu)，而避免圖5的結(jié)構(gòu)，也就是所謂的“平衡”問題。實際使用的B樹都是在原B樹的基礎(chǔ)上加上平衡算法，即“平衡二叉樹”，如何保持B樹結(jié)點分布均勻的平衡算法是平衡二叉樹的關(guān)鍵，這里不再詳述。

三、解決方案

1.內(nèi)存B樹結(jié)構(gòu)

圖5 多次插入或刪除操作后結(jié)構(gòu)

這里使用緩沖來達到加快B樹的查詢和減少內(nèi)存占用的目的，B樹的基本結(jié)構(gòu)見圖6所示。

內(nèi)存中的B樹只包含了部分節(jié)點，主要是包含了前面的一級或者多級節(jié)點。當(dāng)在樹上行走的時候，如果遇到節(jié)點不在樹上時，就到緩沖或者磁盤去尋找。B樹并不把獲得的節(jié)點掛到自己上面。內(nèi)存節(jié)點集合（即緩沖）是一個簡單的緩沖結(jié)構(gòu)，它通過某種策略來決定哪些節(jié)點需要被淘汰。磁盤節(jié)點集合是把節(jié)點保存到磁盤的集合，它提供了讀取磁盤節(jié)點的接口。

圖6 B樹的基本結(jié)構(gòu)2.內(nèi)存節(jié)點集合

在內(nèi)存節(jié)點集合中，每個節(jié)點由一個id進行標(biāo)示，這個id是唯一的（或許它表示這個節(jié)點在磁盤中的位置）。每個節(jié)點同時還有一個dirty標(biāo)志，用來標(biāo)示這個節(jié)點是否被改變了，被改變的節(jié)點由外部控制以某個策略（未定）刷新到磁盤節(jié)點集合。一般的說，當(dāng)節(jié)點被淘汰出緩沖的時候，需要檢測一下其dirty標(biāo)志，決定是否需要刷新到磁盤上。

內(nèi)存B樹新構(gòu)建的節(jié)點除了保存到磁盤節(jié)點集合以外，可能還會保存到內(nèi)存節(jié)點集合。

3.磁盤節(jié)點集合

磁盤節(jié)點集合同樣通過id來標(biāo)示一個節(jié)點。磁盤節(jié)點集合的結(jié)構(gòu)比較復(fù)雜，目前暫時把磁盤節(jié)點集合映射到單一文件上，將來可能會把磁盤節(jié)點結(jié)合映射到多個文件上面，比如，把B樹的基本信息和節(jié)點數(shù)據(jù)集分離），這個文件的結(jié)構(gòu)見圖7所示。

圖7 磁盤節(jié)點映射文件結(jié)構(gòu)磁盤節(jié)點集合支持幾種基本的操作，具體操作介紹如下。

3.1加入新的節(jié)點

加入新的節(jié)點到磁盤節(jié)點集合的時候，直接把節(jié)點數(shù)據(jù)加入到文件的最后面，同時把基本信息寫入到B樹基本信息里面。

3.2修改節(jié)點

當(dāng)某個節(jié)點被修改的時候，情況比增加一個節(jié)點要復(fù)雜一點。在某個節(jié)點被修改的時候，通過讀取B樹基本信息，獲得這個節(jié)點的原始占用長度，如果這個長度比新的長度大，那么，直接在原始位置覆蓋新數(shù)據(jù)上去；否則，刪除原始節(jié)點，加入新的節(jié)點進去，同時刷新B樹基本信息。

3.3刪除節(jié)點

刪除一個節(jié)點的時候，直接把節(jié)點信息從B樹基本信息里面刪除即可。

四、 提升到B*樹

所謂的B*樹是指B樹的2-3分裂規(guī)則。普通的B樹是1-2分裂規(guī)則，即保證節(jié)點（除了頭）至少有50%的空間占用。而2-3分裂規(guī)則是保證節(jié)點有67%的空間占用?？紤]到B*樹實現(xiàn)的復(fù)雜性，本方案暫時不處理空間占用的問題。如果將來有必要，再做這個方面的考慮。同理，對于號稱難度超高的3-4分裂規(guī)則，更不在考慮之列。

五、小結(jié)

文中介紹了B Tree文件系統(tǒng)的設(shè)計問題，給出了B樹的基本信息，并討論了B樹的整個操作過程，得出了提高數(shù)據(jù)查詢效率的主要思想，解決了海量文檔的查詢辦法。

參考文獻：

[1]楊利，昌月樓著.并行數(shù)據(jù)庫技術(shù).長沙：國防科技大學(xué)出版社，2000[2]張華，顧紅飛，劉濤.基于B+ 樹的文本信息檢索技術(shù)[J].皖西學(xué)院學(xué)報，2010.

基金項目：蘇州工業(yè)職業(yè)技術(shù)學(xué)院院級課題《云計算環(huán)境下基于智能終端的計算機軟件開發(fā)技術(shù)分析》 項目編號：SGKB201411。