基于B+樹的數(shù)據(jù)索引存儲(chǔ)

耿慶田,狄 婧,常 亮,趙宏偉

(1.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,長(zhǎng)春 130012；2.長(zhǎng)春師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,長(zhǎng)春 130032；3.長(zhǎng)春師范大學(xué) 網(wǎng)絡(luò)中心,長(zhǎng)春 130032)

目前,索引技術(shù)廣泛應(yīng)用于數(shù)據(jù)庫(kù)中數(shù)字?jǐn)?shù)據(jù)的搜索查詢,B+樹由于其自身的特點(diǎn)決定其適合應(yīng)用于數(shù)據(jù)索引系統(tǒng).在B+樹應(yīng)用中,其節(jié)點(diǎn)記錄了每個(gè)子節(jié)點(diǎn)附加的數(shù)據(jù)信息,并將鍵值和附加數(shù)據(jù)相結(jié)合.一棵節(jié)點(diǎn)數(shù)量很多的B+樹,在構(gòu)建過程中時(shí)間和空間開銷也較大,因此,有必要將B+樹事先寫入磁盤.不同類型的節(jié)點(diǎn)所需空間和實(shí)際附加數(shù)據(jù)大小直接關(guān)聯(lián),節(jié)點(diǎn)讀取效率及其存儲(chǔ)介質(zhì)讀取方式直接關(guān)聯(lián).為了有效組織樹節(jié)點(diǎn)信息單元,可采用多級(jí)位圖鏈表方式進(jìn)行管理[1-3].

B+樹特性:1) B+樹中子樹節(jié)點(diǎn)和關(guān)鍵字的數(shù)量相同;2) 關(guān)鍵字和葉子節(jié)點(diǎn)相對(duì)應(yīng)并且是有序的;3) 非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù);4) 非葉子節(jié)點(diǎn)被當(dāng)做索引部分,葉子節(jié)點(diǎn)包含子樹的關(guān)鍵字;5) 隨機(jī)和順序查找可同時(shí)進(jìn)行[4-6].

1 B+樹的存儲(chǔ)方式

1.1 系統(tǒng)對(duì)B+樹節(jié)點(diǎn)的管理 樹節(jié)點(diǎn)大小可能和存儲(chǔ)單元大小吻合,文件系統(tǒng)的一個(gè)邏輯層物理頁標(biāo)準(zhǔn)大小是512字節(jié),如果節(jié)點(diǎn)附加信息存儲(chǔ)在其他存儲(chǔ)單元,則節(jié)點(diǎn)的物理大小將遠(yuǎn)小于一個(gè)物理頁.B+樹節(jié)點(diǎn)分為根節(jié)點(diǎn)、內(nèi)節(jié)點(diǎn)和葉子節(jié)點(diǎn)3種類型.這3種節(jié)點(diǎn)的物理單元大小可能不同.作為B+樹存儲(chǔ),一個(gè)系統(tǒng)需要存儲(chǔ)的B+樹數(shù)量并不確定.如果選擇對(duì)B+樹3種節(jié)點(diǎn)類型分開存儲(chǔ),并對(duì)多個(gè)B+樹進(jìn)行統(tǒng)一管理,則結(jié)構(gòu)清晰且易于維護(hù).每棵B+樹的分配將由3種不同管理類型負(fù)責(zé)分配,由維護(hù)這3類節(jié)點(diǎn)的系統(tǒng)統(tǒng)一刪除和分配.這種方式的弊端是對(duì)于任意一棵B+樹存儲(chǔ),都可能是分散的.在訪問過程中會(huì)對(duì)分散在不同物理頁的節(jié)點(diǎn)進(jìn)行讀取和其他操作,系統(tǒng)I/O開銷負(fù)載較大.其中節(jié)點(diǎn)刪除也會(huì)導(dǎo)致存儲(chǔ)碎片增多.

系統(tǒng)通過構(gòu)建一種上一層位圖管理方法實(shí)現(xiàn)文件中節(jié)點(diǎn)鏈表的申請(qǐng)與釋放操作.B+樹中一些節(jié)點(diǎn)的位圖區(qū)在系統(tǒng)數(shù)據(jù)初始化時(shí)被記錄,同時(shí)構(gòu)建相應(yīng)級(jí)別的管理模型.

1.2 B+樹節(jié)點(diǎn)的構(gòu)成 為提高對(duì)B+樹各種操作的效率,增加磁盤空間利用率,需要把相同種類的節(jié)點(diǎn)存儲(chǔ)在連續(xù)頁面上,并對(duì)B+樹節(jié)點(diǎn)種類實(shí)行單一管理.這樣可在操作過程中充分利用系統(tǒng)的頁緩存存儲(chǔ)臨近節(jié)點(diǎn)特性,增加B+樹下其他節(jié)點(diǎn)在緩存中命中的可能性,從而減少了I/O負(fù)載.由于B+樹中根節(jié)點(diǎn)是唯一的,因此可為B+樹的根節(jié)點(diǎn)與內(nèi)節(jié)點(diǎn)、外節(jié)點(diǎn)配備并共用兩種不同的存儲(chǔ)空間[7].這樣既便于管理又節(jié)省了寶貴的存儲(chǔ)資源.根節(jié)點(diǎn)的地址分配可依據(jù)B+樹狀態(tài)操作.構(gòu)建B+樹時(shí)把根節(jié)點(diǎn)分在葉節(jié)點(diǎn)地址中,當(dāng)樹深度大于1時(shí),則把根節(jié)點(diǎn)分在內(nèi)節(jié)點(diǎn)地址中.為獲得樹中頁面節(jié)點(diǎn)的各種狀態(tài),把節(jié)點(diǎn)頁面的使用區(qū)域分開單獨(dú)管理,這樣可提供快速系統(tǒng)處理接口.因此使用單獨(dú)分離標(biāo)志顯示該頁區(qū)域分配情況.

圖1 物理頁位圖Fig.1 Map of B+ tree node page

如圖1所示,物理頁中存儲(chǔ)3個(gè)區(qū)域：A表示該物理頁內(nèi)節(jié)點(diǎn)區(qū)域(B區(qū)域)位圖;B表示節(jié)點(diǎn)存儲(chǔ)區(qū)域;C表示當(dāng)前頁的下一個(gè)關(guān)聯(lián)頁鏈接地址.當(dāng)有新鍵值插入時(shí),先查看該B+樹節(jié)點(diǎn)物理頁位圖起始處,考慮是否需要構(gòu)建新節(jié)點(diǎn).如果需要,則在物理頁位圖A部分查看是否有閑置的空間,若有則直接插入鍵值；若沒有,則把當(dāng)前節(jié)點(diǎn)分成兩個(gè)葉節(jié)點(diǎn),把新鍵值平分到兩個(gè)葉節(jié)點(diǎn)中,并在兩個(gè)葉節(jié)點(diǎn)的上一層構(gòu)建新節(jié)點(diǎn).兩個(gè)剛生成的葉節(jié)點(diǎn)即變?yōu)樯弦粚庸?jié)點(diǎn)的子節(jié)點(diǎn).本文以物理頁為單位存放相異類型的節(jié)點(diǎn),通過對(duì)系統(tǒng)緩存采用優(yōu)化策略,把B+樹的相關(guān)節(jié)點(diǎn)存儲(chǔ)都盡可能存放在某固定的物理頁或某個(gè)區(qū)域,這樣可使B+樹在存儲(chǔ)介質(zhì)的存放更集中,同時(shí)縮減了I/O讀取次數(shù),提高了系統(tǒng)效率.存儲(chǔ)系統(tǒng)的物理頁都可視為Map位圖,可容納512字節(jié)的數(shù)據(jù),即可容納512個(gè)節(jié)點(diǎn)[8-9],并每個(gè)Map位圖都相關(guān)聯(lián),這樣使B+樹中節(jié)點(diǎn)更易于管理.

2 B+樹操作

2.1 元數(shù)據(jù)的存儲(chǔ) 由于B+樹節(jié)點(diǎn)眾多,壓縮樹節(jié)點(diǎn)信息量,因此可擴(kuò)大一個(gè)節(jié)點(diǎn)物理存儲(chǔ)單元上的分支因子數(shù)量,提高訪問效率.每個(gè)節(jié)點(diǎn)都存放節(jié)點(diǎn)本身的一些位置信息,這些位置信息內(nèi)容有存儲(chǔ)地址及數(shù)據(jù)存放的相關(guān)地址,因此樹中的節(jié)點(diǎn)由子節(jié)點(diǎn)及節(jié)點(diǎn)自身的一些相關(guān)數(shù)據(jù)構(gòu)成,節(jié)點(diǎn)間通過記錄節(jié)點(diǎn)存儲(chǔ)位置進(jìn)行關(guān)聯(lián).鍵值信息單元存儲(chǔ)了每個(gè)鍵值相關(guān)的附加信息,這些附加信息按特定格式存儲(chǔ),B+樹只需記錄附加信息物理位置,即時(shí)讀取.

2.2 讀取部分訪問路徑 從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)只有一條路徑[10-11],此外,其他數(shù)據(jù)與訪問沒有直接關(guān)系.在需要時(shí)讀取,可減輕系統(tǒng)內(nèi)存和I/O負(fù)載,提高系統(tǒng)效率.在樹的操作過程中,根據(jù)所訪問的鍵值尋找根節(jié)點(diǎn)到葉子節(jié)點(diǎn)通路,若B+樹分支節(jié)點(diǎn)較多,可對(duì)樹中所有節(jié)點(diǎn)關(guān)鍵字使用二分查找方法,即可找到下一級(jí)節(jié)點(diǎn),最終查找到葉子節(jié)點(diǎn).數(shù)據(jù)在隨意寫入讀取過程中,隨機(jī)對(duì)不同元數(shù)據(jù)的讀寫操作可能會(huì)產(chǎn)生較多瑣碎數(shù)據(jù)塊,這些數(shù)據(jù)塊分配在不同的存儲(chǔ)頁面,當(dāng)要讀取其中某一數(shù)據(jù)時(shí),需要查閱很多存儲(chǔ)頁面,既消耗了大量的緩存資源,也使查找緩存中數(shù)據(jù)的命中率極大降低,同時(shí)使I/O負(fù)擔(dān)過重,從而使系統(tǒng)的性能下降.本文把B+樹中節(jié)點(diǎn)所包含的數(shù)據(jù)存放在整個(gè)以物理頁面為單位的存儲(chǔ)介質(zhì)上,同時(shí)使用位圖模式支配物理頁面的使用,提高系統(tǒng)的讀取效率.

2.3 鍵值對(duì)比 B+樹中相關(guān)節(jié)點(diǎn)的鍵值可由不同方式表示,可通過排列Hash值或字符串值表示.當(dāng)鍵值在存儲(chǔ)單元存放時(shí),要記錄鏈表中相應(yīng)節(jié)點(diǎn)的地址.當(dāng)對(duì)其他新鍵值進(jìn)行各種操作時(shí),先使用某種順序(或路徑)查找到鏈表中節(jié)點(diǎn)位置的地址,通過對(duì)地址中節(jié)點(diǎn)的內(nèi)容進(jìn)行比較,再確定新鍵值的地址,并記錄.因此,當(dāng)有新鍵值需要做插入或刪除操作時(shí),調(diào)整其節(jié)點(diǎn)的地址即可,并且這種調(diào)整是有序的.

B+樹操作的主要步驟如下：

1) 產(chǎn)生B+樹根節(jié)點(diǎn).當(dāng)B+樹中有新鍵值插入時(shí),先通過鍵值對(duì)比,找到其要插入節(jié)點(diǎn)的地址,然后將該位置的節(jié)點(diǎn)分裂成兩個(gè)節(jié)點(diǎn),在其上一層生成根節(jié)點(diǎn),并記錄這些節(jié)點(diǎn)的地址信息,相應(yīng)B+樹的位圖標(biāo)志信息也需修改.

2) B+樹回寫信息.B+樹根節(jié)點(diǎn)和葉子節(jié)點(diǎn)可能在插入或刪除等操作中進(jìn)行了修改,但其他路徑上相關(guān)節(jié)點(diǎn)內(nèi)容沒有變化.因此,每個(gè)節(jié)點(diǎn)都有相應(yīng)的標(biāo)志位Flush.若Flush=1,則由根節(jié)點(diǎn)對(duì)該葉子節(jié)點(diǎn)進(jìn)行信息回寫.因?yàn)楦?jié)點(diǎn)存放B+樹相關(guān)節(jié)點(diǎn)的信息,因此需通過遞歸回寫完成索引過程.要注意在回寫根節(jié)點(diǎn)前需把B+樹相關(guān)節(jié)點(diǎn)位置的數(shù)據(jù)復(fù)制到根節(jié)點(diǎn)空間.

3) B+樹鍵值插入操作.當(dāng)B+樹中有新鍵值插入時(shí),先遍歷整個(gè)頁面,找空閑位置,把新鍵值放在空閑位置,再查找和新鍵值大小相近的葉子節(jié)點(diǎn),看是否有空閑位置,若有位置則直接插入新鍵值,若沒有空位置,則該節(jié)點(diǎn)自動(dòng)分裂成兩個(gè)新節(jié)點(diǎn),并把新鍵值插在新節(jié)點(diǎn)位置,且新節(jié)點(diǎn)鍵值的數(shù)量≥1/2鍵值數(shù).把新節(jié)點(diǎn)中鍵值大的遞歸向上插在其上一層節(jié)點(diǎn)中,一直插到根節(jié)點(diǎn)位置.如果根節(jié)點(diǎn)沒有空位置,則根節(jié)點(diǎn)也分裂成兩個(gè)節(jié)點(diǎn),同時(shí)在其上層生成新的根節(jié)點(diǎn).

2.4 B+樹節(jié)點(diǎn)鍵值刪除 如果要?jiǎng)h除某一鍵值K,則先要找到鍵值K所在的葉子節(jié)點(diǎn).算法如下：

1) 把找到放置鍵值K葉子節(jié)點(diǎn)的索引內(nèi)容刪除.當(dāng)前鍵值后的葉子節(jié)點(diǎn)如果為空,則回收已經(jīng)分配的樹節(jié)點(diǎn)空間;如果被刪除節(jié)點(diǎn)鍵的數(shù)量大于或等于B+樹中節(jié)點(diǎn)鍵的最小數(shù)量,則操作結(jié)束；

2) 如果被刪除葉子節(jié)點(diǎn)兄弟節(jié)點(diǎn)的鍵值數(shù)小于B+樹中節(jié)點(diǎn)鍵最小數(shù)量,則把該節(jié)點(diǎn)的鍵值移到被刪除的葉子節(jié)點(diǎn)位置,合并兄弟節(jié)點(diǎn),刪除父節(jié)點(diǎn)位置的鍵值信息,其相應(yīng)的鍵值也要修改；

3) 若修改后父節(jié)點(diǎn)位置的鍵值和B+樹的條件一致,刪除操作結(jié)束；否則,一直遞歸向上到根節(jié)點(diǎn)進(jìn)行刪除操作.

圖2 B+樹(M=2)Fig.2 B+ Tree(M=2)

對(duì)于以字符串為單位存儲(chǔ)鍵值的情況,可在存儲(chǔ)介質(zhì)中存儲(chǔ)鍵值內(nèi)容,在刪除葉子節(jié)點(diǎn)而沒有影響到內(nèi)節(jié)點(diǎn)的情況下,作為樹的存儲(chǔ),需為內(nèi)節(jié)點(diǎn)含有相關(guān)鍵值節(jié)點(diǎn)做調(diào)整,把鍵值更換為子樹做左節(jié)點(diǎn)鍵值,更新其與鍵值的元數(shù)據(jù).圖2為對(duì)節(jié)點(diǎn)刪除和調(diào)整的過程.由圖2可見,如刪除節(jié)點(diǎn)35時(shí),需在查找路徑上記錄刪除鍵值節(jié)點(diǎn)的位置,最后,將最左值38鍵值信息寫入根節(jié)點(diǎn),從而避免了鍵值信息的額外存儲(chǔ).

3 隨機(jī)存儲(chǔ)與位圖存儲(chǔ)對(duì)比

下面對(duì)隨機(jī)存儲(chǔ)和位圖存儲(chǔ)兩種存儲(chǔ)方式進(jìn)行對(duì)比,同等規(guī)模的存儲(chǔ)會(huì)使用不同數(shù)量扇區(qū),讀取扇區(qū)次數(shù)不同.對(duì)含有100個(gè)節(jié)點(diǎn)的4階B+樹進(jìn)行存儲(chǔ),采用集中存儲(chǔ)的存儲(chǔ)方式,模擬器讀寫對(duì)比測(cè)試結(jié)果列于表1.

綜上所述,索引是影響數(shù)字?jǐn)?shù)據(jù)庫(kù)查找性能因素之一[12],較好的索引機(jī)制可提高檢索數(shù)據(jù)速度,并能提高數(shù)據(jù)空間利用率.實(shí)驗(yàn)結(jié)果表明,本文在B+樹節(jié)點(diǎn)存儲(chǔ)的情況下訪問鍵值信息,速度得到較大提升.同時(shí),B+樹存儲(chǔ)的管理需耗費(fèi)一定資源,由于節(jié)點(diǎn)訪問次數(shù)不同,若將常訪問的節(jié)點(diǎn)放入節(jié)點(diǎn)緩存,則可減輕系統(tǒng)查詢負(fù)載,提高系統(tǒng)性能,并可通過權(quán)值進(jìn)行調(diào)整,根據(jù)權(quán)值因子做出動(dòng)態(tài)調(diào)整,提前命中需要存儲(chǔ)在葉子節(jié)點(diǎn)的附加信息.對(duì)B+樹多任務(wù)訪問,避免了讀寫操作沖突,設(shè)置鎖機(jī)制,避免了節(jié)點(diǎn)調(diào)整沖突.

表1 模擬器讀寫的對(duì)比測(cè)試Table 1 Comparative reading and writing test

[1] LIU Cai-ping,LI Ren-fa,LIU Xi-ping.An Improved B+-Tree Access Method Based on Embedded Databases [J].Computer Engineering &Science,2007,29(1):101-102.(劉彩蘋,李仁發(fā),劉喜蘋.面向嵌入式數(shù)據(jù)庫(kù)的改進(jìn)B+樹索引機(jī)制 [J].計(jì)算機(jī)工程與科學(xué),2007,29(1):101-102.)

[2] CHEN Su,Doi B C,Tan K L,et al.ST2B-Tree:A Self-tunable Spatio-Temporal B+-Tree Index for Moving Objects [C]//Proc of SIGMOD’08.New York:ACM Press,2008:29-42.

[3] XING Wei,ZHANG Shou-zhi,SHI Bo-le.B+Tree Index for Moving Objects Based on Two-Level Grids [J].Computer Engineering,2011,37(2):30-33.(邢偉,張守志,施伯樂.一種基于二層網(wǎng)格的移動(dòng)對(duì)象B+樹索引 [J].計(jì)算機(jī)工程,2011,37(2):30-33.)

[4] DENG Pan,LIU Gong-shen.Effective Storage Structure of Inverted Index [J].Computer Engineering and Applications,2008,44(31):149-152.(鄧攀,劉功申.一種高效的倒排索引存儲(chǔ)結(jié)構(gòu) [J].計(jì)算機(jī)工程與應(yīng)用,2008,44(31)：149-152.)

[5] Wires J,Feeley M J.Secure File System Versioning at the Block Level [C]//Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems.New York:ACM,2007:203-215.

[6] Yu C,Bailey J,Montefusco J,et al.Enhancing the B+Tree by Dynamic Node Popularity Caching[J].Information Processing Letters,2010,110(7):268-273.

[7] ZHANGSUN Ni-ni,ZHANG Yi-kun,HUA Deng-xin,et al.Hybrid Index Structure Based on B+ Tree [J].Computer Engineering,2012,38(14):35-37.(長(zhǎng)孫妮妮,張毅坤,華燈鑫,等.一種基于B+樹的混合索引結(jié)構(gòu) [J].計(jì)算機(jī)工程,2012,38(14):35-37.)

[8] LIU Xiao-zhu,PENG Zhi-yong,CHEN Xu.An Efficient Random Access Block Inverted File Self-index Technology [J].Chinese Journal of Computers,2010,33(6):977-987.(劉小珠,彭智勇,陳旭.高效的隨機(jī)訪問分塊倒排文件自索引技術(shù) [J].計(jì)算機(jī)學(xué)報(bào),2010,33(6):977-987.)

[9] ZHANG Li-jun,LI Zhan-huai,CHEN Qun,et al.Classifying XML Documents Based on Term Semantics [J].Journal of Jilin University:Engineering and Technology Edition,2012,42(6):1510-1514.(張利軍,李戰(zhàn)懷,陳群,等.基于關(guān)鍵字語義信息的XML文檔分類 [J].吉林大學(xué)學(xué)報(bào):工學(xué)版,2012,42(6):1510-1514.)

[10] LIU Xiao-zhu.Efficient Maintenance Scheme of Inverted Index for Large-Scale Full-Text Retrieval [C]//Proc of International Conf on Future Computer and Communication.Piscataway:IEEE Press,2010:565-570.

[11] CHEN Tian-huang,YANG Zhi-yong.The Improvement Based on the B+ Tree Index Mechanism [C]//International Conference on Wireless Communications,Networking and Mobile Computing.Piscataway:IEEE Press,2007:3139-3142.

[12] SUN Yuan,CHEN He-xin,CHEN Mian-shu,et al.Multimedia High-Level Semantic Framework and Retrieval Algorithm [J].Journal of Jilin University:Engineering and Technology Edition,2011,41(1):244-248.(孫元,陳賀新,陳綿書,等.多媒體高層語義框架及檢索算法 [J].吉林大學(xué)學(xué)報(bào):工學(xué)版,2011,41(1):244-248.)