基于B+樹的數據索引存儲

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

(1.吉林大學 計算機科學與技術學院,長春 130012；2.長春師范大學 計算機科學與技術學院,長春 130032；3.長春師范大學 網絡中心,長春 130032)

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

B+樹特性:1) B+樹中子樹節點和關鍵字的數量相同;2) 關鍵字和葉子節點相對應并且是有序的;3) 非葉子節點不存儲數據;4) 非葉子節點被當做索引部分,葉子節點包含子樹的關鍵字;5) 隨機和順序查找可同時進行[4-6].

1 B+樹的存儲方式

1.1 系統對B+樹節點的管理 樹節點大小可能和存儲單元大小吻合,文件系統的一個邏輯層物理頁標準大小是512字節,如果節點附加信息存儲在其他存儲單元,則節點的物理大小將遠小于一個物理頁.B+樹節點分為根節點、內節點和葉子節點3種類型.這3種節點的物理單元大小可能不同.作為B+樹存儲,一個系統需要存儲的B+樹數量并不確定.如果選擇對B+樹3種節點類型分開存儲,并對多個B+樹進行統一管理,則結構清晰且易于維護.每棵B+樹的分配將由3種不同管理類型負責分配,由維護這3類節點的系統統一刪除和分配.這種方式的弊端是對于任意一棵B+樹存儲,都可能是分散的.在訪問過程中會對分散在不同物理頁的節點進行讀取和其他操作,系統I/O開銷負載較大.其中節點刪除也會導致存儲碎片增多.

系統通過構建一種上一層位圖管理方法實現文件中節點鏈表的申請與釋放操作.B+樹中一些節點的位圖區在系統數據初始化時被記錄,同時構建相應級別的管理模型.

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

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

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

2 B+樹操作

2.1 元數據的存儲 由于B+樹節點眾多,壓縮樹節點信息量,因此可擴大一個節點物理存儲單元上的分支因子數量,提高訪問效率.每個節點都存放節點本身的一些位置信息,這些位置信息內容有存儲地址及數據存放的相關地址,因此樹中的節點由子節點及節點自身的一些相關數據構成,節點間通過記錄節點存儲位置進行關聯.鍵值信息單元存儲了每個鍵值相關的附加信息,這些附加信息按特定格式存儲,B+樹只需記錄附加信息物理位置,即時讀取.

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

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

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

1) 產生B+樹根節點.當B+樹中有新鍵值插入時,先通過鍵值對比,找到其要插入節點的地址,然后將該位置的節點分裂成兩個節點,在其上一層生成根節點,并記錄這些節點的地址信息,相應B+樹的位圖標志信息也需修改.

2) B+樹回寫信息.B+樹根節點和葉子節點可能在插入或刪除等操作中進行了修改,但其他路徑上相關節點內容沒有變化.因此,每個節點都有相應的標志位Flush.若Flush=1,則由根節點對該葉子節點進行信息回寫.因為根節點存放B+樹相關節點的信息,因此需通過遞歸回寫完成索引過程.要注意在回寫根節點前需把B+樹相關節點位置的數據復制到根節點空間.

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

2.4 B+樹節點鍵值刪除 如果要刪除某一鍵值K,則先要找到鍵值K所在的葉子節點.算法如下：

1) 把找到放置鍵值K葉子節點的索引內容刪除.當前鍵值后的葉子節點如果為空,則回收已經分配的樹節點空間;如果被刪除節點鍵的數量大于或等于B+樹中節點鍵的最小數量,則操作結束；

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

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

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

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

3 隨機存儲與位圖存儲對比

下面對隨機存儲和位圖存儲兩種存儲方式進行對比,同等規模的存儲會使用不同數量扇區,讀取扇區次數不同.對含有100個節點的4階B+樹進行存儲,采用集中存儲的存儲方式,模擬器讀寫對比測試結果列于表1.

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

表1 模擬器讀寫的對比測試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.(劉彩蘋,李仁發,劉喜蘋.面向嵌入式數據庫的改進B+樹索引機制 [J].計算機工程與科學,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.(邢偉,張守志,施伯樂.一種基于二層網格的移動對象B+樹索引 [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.(鄧攀,劉功申.一種高效的倒排索引存儲結構 [J].計算機工程與應用,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.(長孫妮妮,張毅坤,華燈鑫,等.一種基于B+樹的混合索引結構 [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].計算機學報,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.(張利軍,李戰懷,陳群,等.基于關鍵字語義信息的XML文檔分類 [J].吉林大學學報:工學版,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].吉林大學學報:工學版,2011,41(1):244-248.)