B Tree文件系統(tǒng)設(shè)計(jì)方案

郝愛語(yǔ)

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

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

一、提出問題

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

表1 查詢操作需求明細(xì)

二、B樹概述

1. B樹定義

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

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

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

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

3） 每個(gè)葉子節(jié)點(diǎn)的深度都是一樣的

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

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

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

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

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

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

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

1） 節(jié)點(diǎn)ID

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

3） 節(jié)點(diǎn)的層次

4） 節(jié)點(diǎn)的類型

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

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

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

3. B樹基本信息

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

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

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

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

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

4. B樹的一般原則

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

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

2） B樹的高度 <= 4

5. B樹的搜索

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

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

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

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

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

三、解決方案

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

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

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

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

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

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

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

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

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

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

3.1加入新的節(jié)點(diǎn)

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

3.2修改節(jié)點(diǎn)

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

3.3刪除節(jié)點(diǎn)

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

四、 提升到B*樹

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

五、小結(jié)

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

參考文獻(xiàn)：

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

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