基于FD-tree的閃存數(shù)據(jù)庫索引技術(shù)研究.pdf

1、閃存由于高效的隨機(jī)讀、低功耗和無噪音等優(yōu)點，被認(rèn)為有望取代磁盤成為數(shù)據(jù)庫的永久性存儲介質(zhì)。閃存一些不同于磁盤的I/O特性，使得傳統(tǒng)的基于磁盤I/O的算法和數(shù)據(jù)結(jié)構(gòu)，如B+樹索引等，并不能直接應(yīng)用到閃存上。由于樹形索引是關(guān)系型數(shù)據(jù)庫中重要的數(shù)據(jù)訪問方式之一，對基于閃存的關(guān)系型數(shù)據(jù)庫的性能有很大影響，因此許多工作都對閃存上的樹形索引進(jìn)行了研究。FD-Tree即是一種針對閃存所設(shè)計的索引樹結(jié)構(gòu)，針對閃存讀寫速度的不對稱，F(xiàn)D-Tree將隨機(jī)寫

2、操作轉(zhuǎn)化為批量的順序?qū)懖僮?，從而提高了索引的效率?br>　　 然而FD-tree在實際的數(shù)據(jù)庫應(yīng)用中仍有明顯不足。FD-Tree在初始化裝載大量數(shù)據(jù)時，會進(jìn)行多次的層級歸并操作，產(chǎn)生了大量讀寫閃存操作，嚴(yán)重影響了系統(tǒng)性能。本文提出了一種新的FD-Tree裝載算法，在進(jìn)行層間歸并時，將整層分為區(qū)間逐段歸并，減少了I/O的次數(shù)。通過在真實閃存上的性能實驗評測，證明了新裝載算法在I/O次數(shù)和CPU時間上比普通的FD-Tree插入算法均有很

3、大的提高，是一種實際高效的算法成果。
　　 由于FD-tree每層頁面都是排好序的索引項，非常適合進(jìn)行壓縮。本文設(shè)計了針對FD-tree索引項鍵值的壓縮算法，對索引項的鍵值，以及rowid字段均能進(jìn)行壓縮。壓縮算法保持了FD-tree原有的各項操作的復(fù)雜度的情況下，能夠帶來很好的壓縮率和查詢性能的提升。通過 TPC-H1GB鍵值索引數(shù)據(jù)的測試證明，本文的索引數(shù)據(jù)壓縮算法，能夠為FD-tree索引節(jié)省約一半的存儲空間，同時帶來約2