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

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

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

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