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

1、隨著信息化技術(shù)的發(fā)展和Web2.0時(shí)代的到來(lái)，數(shù)據(jù)資源的類(lèi)型和規(guī)模不斷擴(kuò)大，社會(huì)發(fā)展已經(jīng)進(jìn)入到大數(shù)據(jù)時(shí)代。大數(shù)據(jù)時(shí)代的來(lái)臨，給索引技術(shù)和數(shù)據(jù)庫(kù)系統(tǒng)的發(fā)展帶來(lái)了巨大的機(jī)遇和挑戰(zhàn)。B+樹(shù)索引是一種索引有序數(shù)據(jù)的高效索引方式，其在文件系統(tǒng)和數(shù)據(jù)庫(kù)系統(tǒng)建立索引等方面起著重要作用。然而，隨著數(shù)據(jù)規(guī)模的不斷擴(kuò)大，B+樹(shù)發(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、些日益增長(zhǎng)的數(shù)據(jù)顯得十分必要。
　　本文首先介紹了常見(jiàn)的幾種索引結(jié)構(gòu)，包括線性表索引、順序表索引、散列索引和樹(shù)形索引，著重闡述了樹(shù)形索引結(jié)構(gòu)中的B-樹(shù)索引和B+樹(shù)索引。在比較分析B-樹(shù)和B+樹(shù)索引機(jī)制的優(yōu)缺點(diǎn)的基礎(chǔ)上，結(jié)合當(dāng)前大數(shù)據(jù)時(shí)代的背景，針對(duì)經(jīng)典B+樹(shù)索引機(jī)制出現(xiàn)的查詢(xún)性能下降和空間利用率低的問(wèn)題，提出了一種基于動(dòng)態(tài)結(jié)點(diǎn)流行度的B+樹(shù)索引結(jié)構(gòu)-DNCPB+-tree(Dynamic Node Cache Popularity

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