基于PCM的B+-Tree索引的研究.pdf

1、隨著科技的高速發(fā)展和大數(shù)據(jù)時(shí)代的到來(lái)，數(shù)據(jù)的存儲(chǔ)需求和對(duì)響應(yīng)時(shí)間的要求都在不斷提高，僅僅從軟件層面上解決存儲(chǔ)問(wèn)題比較困難，需要有新技術(shù)來(lái)擺脫磁盤(pán)的機(jī)械特性限制。近年來(lái)，材料技術(shù)的進(jìn)步促進(jìn)了新型存儲(chǔ)器的飛速發(fā)展，為高效能大數(shù)據(jù)存儲(chǔ)和管理研究帶來(lái)了新機(jī)遇。繼Flash之后，國(guó)內(nèi)外許多研究者開(kāi)始關(guān)注以相變存儲(chǔ)器PCM為代表的非易失存儲(chǔ)器。
　　可字節(jié)尋址、非易失、低能耗和大容量等特點(diǎn)，讓PCM成為當(dāng)下可替代傳統(tǒng)內(nèi)存介質(zhì)DRAM的熱門(mén)新型

2、存儲(chǔ)器。但由于PCM與DRAM特性的不同，已有的數(shù)據(jù)管理方法不適用于PCM。首先，DRAM是易失型介質(zhì)，因此一般用來(lái)存儲(chǔ)計(jì)算過(guò)程中的動(dòng)態(tài)數(shù)據(jù);而PCM是非易失介質(zhì)，既可以存儲(chǔ)動(dòng)態(tài)計(jì)算數(shù)據(jù)，也可以存儲(chǔ)文件等持久的靜態(tài)數(shù)據(jù)。其次，主存級(jí)PCM的引入并不能完全取代DRAM，雖然PCM讀性能較好，但寫(xiě)代價(jià)相對(duì)較高，而且寫(xiě)次數(shù)有限，因此在存儲(chǔ)架構(gòu)中依然需要借助DRAM來(lái)保證其高效性。因此傳統(tǒng)的內(nèi)存數(shù)據(jù)管理機(jī)制，包括空間分配、存儲(chǔ)組織、索引等不能直

3、接適用于PCM。本文針對(duì)內(nèi)存數(shù)據(jù)管理機(jī)制中的索引算法，探討如何優(yōu)化傳統(tǒng)的索引機(jī)制，以讓其適用于基于PCM的內(nèi)存數(shù)據(jù)管理。
　　具體而言，本文的主要貢獻(xiàn)有:
　　(1)提出了溢出類(lèi)型B+-tree(OB+-tree)索引的讀訪(fǎng)問(wèn)優(yōu)化算法CB+-tree。本文首先對(duì)結(jié)點(diǎn)的讀寫(xiě)傾向性進(jìn)行了定義，分析了讀寫(xiě)傾向性判斷方法，然后詳盡闡述了利用結(jié)點(diǎn)的讀寫(xiě)傾向進(jìn)行溢出鏈調(diào)整的策略，以及優(yōu)化后索引的查詢(xún)、插入和刪除操作方法。最后通過(guò)對(duì)比實(shí)驗(yàn)

4、，證明溢出鏈優(yōu)化方法可以有效的減少索引對(duì)PCM的讀次數(shù)，與OB+-tree相比減少約25％讀次數(shù)，平均整體時(shí)間性能提高約15％。
　　(2)提出了利用DRAM作為輔助存儲(chǔ)的溢出類(lèi)型B+-tree（OB+-tree）索引的優(yōu)化算法XB+-tree。在DRAM和PCM混合主存架構(gòu)中，以DRAM的高寫(xiě)性能來(lái)彌補(bǔ)PCM的缺點(diǎn)，結(jié)合索引結(jié)點(diǎn)具有讀寫(xiě)傾向性的特點(diǎn)，將少量具有寫(xiě)傾向的結(jié)點(diǎn)遷移至DRAM上;同時(shí)，為小容量的DRAM提出了索引結(jié)點(diǎn)管