B Tree文件系統(tǒng)設計方案

郝愛語

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

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

一、提出問題

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

表1 查詢操作需求明細

二、B樹概述

1. B樹定義

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

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

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

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

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

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

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

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

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

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

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

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

1） 節(jié)點ID

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

3） 節(jié)點的層次

4） 節(jié)點的類型

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

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

內存中的葉子節(jié)點還包含了dirty屬性，標明節(jié)點是否被修改了，而緩沖中的節(jié)點還會有對應的權重。

3. B樹基本信息

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

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

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

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

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

4. B樹的一般原則

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

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

2） B樹的高度 <= 4

5. B樹的搜索

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

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

圖2 插入結點結構（1）

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

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

三、解決方案

1.內存B樹結構

圖5 多次插入或刪除操作后結構

這里使用緩沖來達到加快B樹的查詢和減少內存占用的目的，B樹的基本結構見圖6所示。

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

圖6 B樹的基本結構2.內存節(jié)點集合

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

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

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

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

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

3.1加入新的節(jié)點

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

3.2修改節(jié)點

當某個節(jié)點被修改的時候，情況比增加一個節(jié)點要復雜一點。在某個節(jié)點被修改的時候，通過讀取B樹基本信息，獲得這個節(jié)點的原始占用長度，如果這個長度比新的長度大，那么，直接在原始位置覆蓋新數(shù)據上去；否則，刪除原始節(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)的復雜性，本方案暫時不處理空間占用的問題。如果將來有必要，再做這個方面的考慮。同理，對于號稱難度超高的3-4分裂規(guī)則，更不在考慮之列。

五、小結

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

參考文獻：

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

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