CF-HNLBI：一種新的閃存數(shù)據(jù)庫B+樹索引.pdf

1、閃存是一種新型的電可擦除可編程只讀存儲器，具有非易失、讀寫速度快、抗震性能好、低功耗、體積小等特性。隨著閃存容量的不斷增加和價格的逐漸下降，閃存相對于傳統(tǒng)機械硬盤具有了更加明顯的競爭優(yōu)勢，已經(jīng)廣泛應(yīng)用于嵌入式系統(tǒng)、航空航天、消費電子等領(lǐng)域。目前，隨著閃存的不斷發(fā)展，已經(jīng)有越來越多的企業(yè)開始使用閃存作為底層的存儲設(shè)備。
　　但是，閃存設(shè)備自身也存在一些缺點:(1)閃存的單位容量價格仍然高于傳統(tǒng)的機械硬盤且生命周期更短;(2)閃存中數(shù)

2、據(jù)的擦除是以塊為單位的，一個數(shù)據(jù)塊中包含固定數(shù)量的連續(xù)頁，而閃存數(shù)據(jù)的讀寫是以頁為單位的;(3)閃存更新數(shù)據(jù)的方式為異地更新;(4)閃存的讀寫速度是不一致的，其讀操作由于不需要尋道時間，因而具有良好的讀取數(shù)據(jù)的性能，但其寫操作和擦除操作相對于讀操作而言則很慢。數(shù)據(jù)庫系統(tǒng)在選擇閃存作為存儲設(shè)備時，如果使用傳統(tǒng)的數(shù)據(jù)庫B+樹索引結(jié)構(gòu)，往往無法充分發(fā)揮閃存的優(yōu)勢，因而需要針對閃存獨有的特性而進行一定的優(yōu)化。已有的基于閃存的數(shù)據(jù)庫索引結(jié)構(gòu)，如B

3、FTL、IBSF以及LA-Tree等，都沒有考慮閃存的異地更新以及寫前擦除等特性，因而無法使閃存數(shù)據(jù)庫系統(tǒng)中獲得更好的整體性能。
　　本文首先提出了一種樸素的HNLBI(Head Node List B+-Tree Indexing)索引，該索引結(jié)構(gòu)大量減少了緩沖區(qū)中的冗余信息，提高了緩沖區(qū)的利用效率，同時通過頭節(jié)點的使用更好地組織了緩沖區(qū)中的更新信息，降低了緩沖區(qū)相關(guān)操作的時間損耗，并且提出了基于最長更新信息鏈表的緩沖區(qū)替換算法

4、，減少了閃存寫操作的次數(shù)。但是HNLBI索引并沒有考慮到數(shù)據(jù)訪問局部性的特點，當B+樹索引中某些結(jié)點被多次訪問時，有可能造成該結(jié)點被頻繁換入換出緩沖區(qū)的情況。因此本文提出了針對HNLBI的改進的索引結(jié)構(gòu)，即CF-HNLBI(Cold-First HeadNode List B+-Tree Indexing)索引，它將緩沖區(qū)分為冷區(qū)和熱區(qū)，當緩沖區(qū)滿時，替換操作僅發(fā)生在冷區(qū)，這使得被頻繁訪問的節(jié)點有更多的機會駐留在緩沖區(qū)中，避免了該類節(jié)點