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

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

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

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

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