基于動(dòng)態(tài)結(jié)點(diǎn)流行度的B+樹索引研究.pdf

1、隨著信息化技術(shù)的發(fā)展和Web2.0時(shí)代的到來，數(shù)據(jù)資源的類型和規(guī)模不斷擴(kuò)大，社會(huì)發(fā)展已經(jīng)進(jìn)入到大數(shù)據(jù)時(shí)代。大數(shù)據(jù)時(shí)代的來臨，給索引技術(shù)和數(shù)據(jù)庫系統(tǒng)的發(fā)展帶來了巨大的機(jī)遇和挑戰(zhàn)。B+樹索引是一種索引有序數(shù)據(jù)的高效索引方式，其在文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)建立索引等方面起著重要作用。然而，隨著數(shù)據(jù)規(guī)模的不斷擴(kuò)大，B+樹發(fā)生結(jié)點(diǎn)分裂時(shí)耗費(fèi)大量時(shí)間，并且其內(nèi)部結(jié)點(diǎn)空間利用率較低，嚴(yán)重地影響了應(yīng)用系統(tǒng)的性能。因此，設(shè)計(jì)出高效合理的索引結(jié)構(gòu)，以管理和組織這

2、些日益增長的數(shù)據(jù)顯得十分必要。
　　本文首先介紹了常見的幾種索引結(jié)構(gòu)，包括線性表索引、順序表索引、散列索引和樹形索引，著重闡述了樹形索引結(jié)構(gòu)中的B-樹索引和B+樹索引。在比較分析B-樹和B+樹索引機(jī)制的優(yōu)缺點(diǎn)的基礎(chǔ)上，結(jié)合當(dāng)前大數(shù)據(jù)時(shí)代的背景，針對(duì)經(jīng)典B+樹索引機(jī)制出現(xiàn)的查詢性能下降和空間利用率低的問題，提出了一種基于動(dòng)態(tài)結(jié)點(diǎn)流行度的B+樹索引結(jié)構(gòu)-DNCPB+-tree(Dynamic Node Cache Popularity

3、 B+-tree)。該索引結(jié)構(gòu)通過修改經(jīng)典B+樹的內(nèi)部結(jié)點(diǎn)結(jié)構(gòu)，提高其空間利用率;通過在葉子結(jié)點(diǎn)引入流行度參數(shù)和在內(nèi)部結(jié)點(diǎn)動(dòng)態(tài)緩存訪問頻率較高的葉子結(jié)點(diǎn)信息，提高其查詢性能。最后實(shí)驗(yàn)采用SQLite開源數(shù)據(jù)庫平臺(tái)，分別就平均I/O開銷和查詢響應(yīng)時(shí)間對(duì)DNCPB+-tree索引和經(jīng)典B+-tree索引進(jìn)行對(duì)比分析，以驗(yàn)證DNCPB+樹索引機(jī)制的有效性。
　　實(shí)驗(yàn)結(jié)果表明:與經(jīng)典B+樹索引機(jī)制相比，盡管DNCPB+-tree的查詢操作