孫 鑒，武曉曉，謝開(kāi)斌，高錦濤，劉凇佐，巫思敏

1.北方民族大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，銀川 750021

2.寧夏大學(xué) 信息工程學(xué)院，銀川 750021

隨著大數(shù)據(jù)時(shí)代的蓬勃發(fā)展，各行各業(yè)對(duì)數(shù)據(jù)存儲(chǔ)提出了更高要求。傳統(tǒng)的磁盤(pán)存儲(chǔ)已無(wú)法滿足大數(shù)據(jù)時(shí)代的存儲(chǔ)需求，因此，經(jīng)過(guò)不斷的研究和創(chuàng)新，閃存誕生。閃存作為一種新型存儲(chǔ)介質(zhì)，由于其具有低功耗、高抗震性[1]等優(yōu)點(diǎn)，很快被應(yīng)用于固態(tài)硬盤(pán)（solid state drive，SSD）[2-3]。

固態(tài)硬盤(pán)，簡(jiǎn)稱固態(tài)盤(pán)[4]，主要是由NANDFLASH存儲(chǔ)芯片陣列構(gòu)成的電子設(shè)備，其內(nèi)部包含控制單元、存儲(chǔ)單元（FLASH芯片、DRAM芯片）以及緩存單元三個(gè)主要部件。與傳統(tǒng)的由磁頭、磁盤(pán)臂、盤(pán)片構(gòu)成的機(jī)械硬盤(pán)磁盤(pán)不同，整個(gè)SSD的內(nèi)部結(jié)構(gòu)中沒(méi)有機(jī)械部件，而是由電子芯片及電路板組成，圖1為SSD基本結(jié)構(gòu)。

從圖1中可以看到固態(tài)硬盤(pán)控制器、閃存陣列、寄存器三個(gè)主要部件的結(jié)構(gòu)。

SSD控制器是重要組件之一，主要有兩個(gè)作用：一是應(yīng)用FTL（flash translation layer）算法控制I/O請(qǐng)求，將數(shù)據(jù)分發(fā)至NANDFLASH芯片上進(jìn)行操作，承擔(dān)SSD中的邏輯地址與NANDFLASH芯片中物理頁(yè)的地址映射。二是調(diào)配N(xiāo)ANDFLASH芯片上的數(shù)據(jù)負(fù)荷，保證磨損均衡。不同廠家應(yīng)用的SSD主控的功能差異較大，這使得SSD整體在讀寫(xiě)操作的性能、整盤(pán)壽命、垃圾回收算法等各個(gè)方面產(chǎn)生很大的差距。

FLASH閃存陣列：NANDFLASH芯片是SSD固態(tài)硬盤(pán)中存儲(chǔ)數(shù)據(jù)的主要介質(zhì)，其數(shù)據(jù)的讀寫(xiě)操作較傳統(tǒng)磁盤(pán)有很大的不同。傳統(tǒng)磁盤(pán)中，數(shù)據(jù)存儲(chǔ)在磁性盤(pán)片上，以扇區(qū)為單位按照扇區(qū)、磁道、柱面、盤(pán)片的層次依次組織數(shù)據(jù)的存放方式，并以機(jī)械方式來(lái)讀寫(xiě)數(shù)據(jù)。但是在SSD固態(tài)硬盤(pán)中，數(shù)據(jù)是存放在NANDFLASH芯片上，以物理頁(yè)為基本的存儲(chǔ)單位，按照物理頁(yè)、物理塊、分組、晶片、芯片的層次結(jié)構(gòu)依次存放，以信號(hào)線和數(shù)據(jù)線的方式來(lái)讀寫(xiě)數(shù)據(jù)。在SSD固態(tài)盤(pán)中，閃存芯片通過(guò)通道（channel）各自獨(dú)立地連接至控制器中，以這種并行的方式組成NANDFLASH芯片陣列。因?yàn)镾SD控制器中的每個(gè)通道可以獨(dú)立工作，所以SSD可以充分發(fā)揮NANDFLASH芯片陣列的并行性，從而獲取非常優(yōu)異的讀寫(xiě)性能。

閃存具有以下幾個(gè)顯著特點(diǎn)：

（1）讀寫(xiě)速度不對(duì)稱：閃存寫(xiě)操作的總體訪問(wèn)延遲比讀操作的總體訪問(wèn)延遲要高很多。一般來(lái)說(shuō)，閃存寫(xiě)延遲比讀延遲高一個(gè)數(shù)量級(jí)[5]。

（2）擦除操作粒度與讀寫(xiě)操作粒度不同，讀寫(xiě)操作的最小單位是頁(yè)[6]，擦除操作的最小單位是塊[7]。

（3）寫(xiě)前擦除[8]：閃存在寫(xiě)頁(yè)面前需要先對(duì)這個(gè)頁(yè)面所在的塊執(zhí)行擦除操作，即閃存不支持原地修改數(shù)據(jù)[9]。為了確保塊內(nèi)原先存儲(chǔ)的數(shù)據(jù)不丟失，必須在執(zhí)行擦除操作之前將該塊的有效頁(yè)面讀取出來(lái)，待擦除操作完成后與需要寫(xiě)入的數(shù)據(jù)一同寫(xiě)回。這一過(guò)程帶來(lái)的實(shí)際寫(xiě)操作數(shù)量遠(yuǎn)比本來(lái)需要寫(xiě)入的數(shù)量多，造成了“寫(xiě)放大”問(wèn)題，同時(shí)帶來(lái)了較大的延遲。為了減少每次更新操作的時(shí)間開(kāi)銷(xiāo)，閃存通常采用異地更新[10]策略，即先把更新數(shù)據(jù)存儲(chǔ)到其他空閑頁(yè)中，將原來(lái)舊數(shù)據(jù)所在的頁(yè)標(biāo)記為無(wú)效頁(yè)[11]，等到垃圾回收[12]時(shí)統(tǒng)一執(zhí)行擦除操作，將原來(lái)舊數(shù)據(jù)所在的頁(yè)變?yōu)榭臻e頁(yè)。此外，垃圾回收會(huì)定期回收無(wú)效頁(yè)。

（4）使用壽命有限：頻繁的寫(xiě)操作會(huì)帶來(lái)大量的擦除操作，而閃存芯片的擦除次數(shù)有限，使得閃存芯片在達(dá)到有限擦除次數(shù)后壽命耗盡，造成嚴(yán)重的數(shù)據(jù)丟失。通常，固態(tài)盤(pán)中設(shè)計(jì)閃存轉(zhuǎn)換層來(lái)實(shí)現(xiàn)磨損均衡，從而延長(zhǎng)閃存的使用壽命。

索引是存儲(chǔ)系統(tǒng)的存儲(chǔ)引擎，是整個(gè)存儲(chǔ)系統(tǒng)的核心，直接決定了存儲(chǔ)系統(tǒng)能夠提供的性能和功能。同時(shí)，索引也是數(shù)據(jù)庫(kù)管理員（database administrator，DBA）用來(lái)分析工作負(fù)載性能最重要的工具之一，因此對(duì)索引技術(shù)的研究尤為重要[13]。由于閃存的物理特性，基于傳統(tǒng)存儲(chǔ)系統(tǒng)的索引結(jié)構(gòu)不能直接應(yīng)用于固態(tài)盤(pán)上，因此，研究適用于固態(tài)盤(pán)的索引結(jié)構(gòu)迫在眉睫。

傳統(tǒng)磁盤(pán)索引結(jié)構(gòu)，如B-tree[14-16]（源碼：https：//github.com/tidwall/btree）通過(guò)減少磁盤(pán)訪問(wèn)次數(shù)來(lái)提高數(shù)據(jù)庫(kù)性能，但是B-tree及其變體[17-18]在執(zhí)行更新操作時(shí)會(huì)產(chǎn)生級(jí)聯(lián)更新[19]現(xiàn)象。級(jí)聯(lián)更新是指當(dāng)葉節(jié)點(diǎn)需要更新時(shí)，由于閃存寫(xiě)前擦除和異地更新的特點(diǎn)，需要先將葉節(jié)點(diǎn)所在的頁(yè)塊全部寫(xiě)入內(nèi)存中，再將更新數(shù)據(jù)和節(jié)點(diǎn)數(shù)據(jù)合并后一起寫(xiě)入新的空閑塊中。同時(shí)，葉節(jié)點(diǎn)對(duì)應(yīng)的父節(jié)點(diǎn)以及更高層的父節(jié)點(diǎn)的指針也要發(fā)生變化，意味著也需將這些父節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)據(jù)寫(xiě)入到新的閃存頁(yè)面中，這樣便會(huì)產(chǎn)生大量的、代價(jià)高昂的閃存寫(xiě)操作。顯然，傳統(tǒng)的B-tree索引在閃存上將出現(xiàn)嚴(yán)重的性能退化現(xiàn)象[20]，特別是在更新操作密集的工作負(fù)載中。因此，不經(jīng)過(guò)任何轉(zhuǎn)換優(yōu)化，直接將B-tree應(yīng)用到閃存上是不可行的，需要對(duì)基于磁盤(pán)設(shè)計(jì)的B-tree進(jìn)行一定程度的修改，使其能夠適配閃存的物理特性，盡量減少針對(duì)閃存的寫(xiě)操作，才能充分發(fā)揮閃存的存儲(chǔ)優(yōu)勢(shì)。

目前基于閃存的索引機(jī)制研究按照索引結(jié)構(gòu)進(jìn)行分類(lèi)，可分為：（1）基于閃存的哈希索引[21]機(jī)制研究，主要聚焦于線性哈希和可擴(kuò)展哈希；（2）基于閃存的樹(shù)型索引機(jī)制研究，主要聚焦于B-tree與R-tree[22-23]；（3）基于閃存的位圖索引機(jī)制研究，主要聚焦于布隆過(guò)濾器[24-25]。

通過(guò)閱讀大量文獻(xiàn)，本文對(duì)面向閃存的樹(shù)型索引機(jī)制的研究進(jìn)行歸類(lèi)和總結(jié)，從索引更新策略的角度切入，將當(dāng)前關(guān)于樹(shù)型索引的研究分為三類(lèi)：（1）延遲更新類(lèi)索引；（2）追加寫(xiě)更新類(lèi)索引；（3）自適應(yīng)動(dòng)態(tài)更新類(lèi)索引。本文詳細(xì)描述了三大類(lèi)別索引結(jié)構(gòu)的核心思想及其具體實(shí)現(xiàn)。希望通過(guò)這樣的總結(jié)歸類(lèi)方法，能夠讓研究者們有所收獲。三類(lèi)所包含的索引結(jié)構(gòu)如表1所示。

表1 索引分類(lèi)Table 1 Index classification

延遲更新方法首先將數(shù)據(jù)更新引發(fā)的索引變化緩存在內(nèi)存中，當(dāng)緩存的數(shù)據(jù)滿足設(shè)定條件時(shí)再執(zhí)行批量更新操作。該方法通過(guò)消除冗余操作和批量提交的方式降低了寫(xiě)操作代價(jià)。

追加寫(xiě)更新的思想如同日志文件系統(tǒng)，直接將更新內(nèi)容追加寫(xiě)到末尾。當(dāng)上一層索引的容量達(dá)到閾值后，執(zhí)行歸并操作，合并至下一層，依次類(lèi)推，直至當(dāng)前索引層不再發(fā)生溢出。在合并的過(guò)程中，一般只產(chǎn)生連續(xù)寫(xiě)操作。

自適應(yīng)動(dòng)態(tài)更新的思想是根據(jù)索引節(jié)點(diǎn)的讀寫(xiě)負(fù)載情況實(shí)時(shí)調(diào)整索引結(jié)構(gòu)。若工作負(fù)載是讀密集型的，則將索引結(jié)構(gòu)自動(dòng)調(diào)整到適合讀密集訪問(wèn)模式的結(jié)構(gòu)，提高讀操作效率[49-50]。

本文的主要貢獻(xiàn)：（1）概述了閃存和樹(shù)型閃存索引的研究現(xiàn)狀以及目前研究所面臨的挑戰(zhàn)；（2）通過(guò)分類(lèi)的方式總結(jié)這些樹(shù)型索引結(jié)構(gòu)采用的主要技術(shù)，并描述了各個(gè)主要技術(shù)的核心思想；（3）討論目前閃存索引研究存在的問(wèn)題，提出未來(lái)的研究方向和趨勢(shì)。

1 延遲更新類(lèi)索引

1.1 BFTL

BFTL（B-tree layer on flash memory）由緩沖區(qū)和節(jié)點(diǎn)轉(zhuǎn)換表組成，當(dāng)針對(duì)B-tree的某個(gè)節(jié)點(diǎn)執(zhí)行插入、刪除或更改操作時(shí)，更新信息將首先被緩存在緩沖區(qū)中；緩沖區(qū)滿后，信息將被更新到閃存中，同時(shí)，BFTL將為這些信息建立對(duì)應(yīng)的索引單元，并將其寫(xiě)入閃存物理頁(yè)中。索引單元和節(jié)點(diǎn)的相對(duì)應(yīng)關(guān)系通過(guò)節(jié)點(diǎn)轉(zhuǎn)換表來(lái)獲得。但BFTL存在以下缺點(diǎn)：（1）由于B-tree的節(jié)點(diǎn)信息分散在不同的物理頁(yè)，訪問(wèn)一個(gè)節(jié)點(diǎn)往往引起多次的讀操作；（2）節(jié)點(diǎn)轉(zhuǎn)換表必須存儲(chǔ)在內(nèi)存中并不斷增長(zhǎng)，這會(huì)消耗大量的內(nèi)存空間；（3）由于BFTL緩沖區(qū)只是按序記錄更新信息，當(dāng)節(jié)點(diǎn)執(zhí)行分裂或其他操作時(shí)容易造成過(guò)多的冗余信息，使得緩沖區(qū)利用率較低。

1.2 IBSF

IBSF（index buffer management scheme）是對(duì)BFTL的優(yōu)化，在閃存上的性能表現(xiàn)更好。作為一種典型的采用延遲更新策略的B-tree索引結(jié)構(gòu)，IBSF取消了節(jié)點(diǎn)轉(zhuǎn)換表，并對(duì)緩沖區(qū)中的信息進(jìn)行了處理，這在一定程度上減少了冗余信息。IBSF的核心思想是：（1）與BFTL不同，當(dāng)緩沖區(qū)中的更新信息數(shù)量達(dá)到一定的閾值時(shí)，IBSF將關(guān)于同一個(gè)節(jié)點(diǎn)的信息寫(xiě)入同一個(gè)閃存物理頁(yè)中，因此不再需要節(jié)點(diǎn)轉(zhuǎn)換表；（2）IBSF刪除緩沖區(qū)中的冗余節(jié)點(diǎn)信息從而推遲寫(xiě)閃存的時(shí)間。因此，IBSF能顯著減少對(duì)閃存的寫(xiě)操作次數(shù)。但I(xiàn)BSF也存在不足：（1）緩沖區(qū)每個(gè)更新單元除記錄更新信息外，還需記錄所屬節(jié)點(diǎn)的信息，造成了信息冗余；（2）更新信息在緩沖區(qū)中是按序存儲(chǔ)的，導(dǎo)致在執(zhí)行增刪改查等操作時(shí)需遍歷整個(gè)緩沖區(qū)；（3）執(zhí)行緩沖區(qū)替換操作時(shí)，IBSF忽略了更新信息訪問(wèn)頻度不均衡的問(wèn)題，導(dǎo)致更新次數(shù)頻繁的節(jié)點(diǎn)被刷新至閃存，帶來(lái)更多的寫(xiě)操作次數(shù)。上述缺陷的存在，使得IBSF在許多實(shí)際應(yīng)用中不能取得很好的效果。

1.3 HNLBI

HNLBI（head node list B-tree indexing）索引是對(duì)IBSF的改進(jìn)，該索引基于最長(zhǎng)節(jié)點(diǎn)鏈表替換算法，將緩沖區(qū)內(nèi)的索引單元重新組合，采用延遲更新的索引優(yōu)化策略。HNLBI索引的主要思想是：（1）若關(guān)于某個(gè)節(jié)點(diǎn)的更新信息首次插入時(shí)，則首先在緩沖區(qū)中為該節(jié)點(diǎn)創(chuàng)建一個(gè)頭節(jié)點(diǎn)，并將該頭節(jié)點(diǎn)加入到頭節(jié)點(diǎn)鏈表中；若待執(zhí)行的是刪除操作，則在頭節(jié)點(diǎn)中創(chuàng)建一個(gè)用于更新節(jié)點(diǎn)刪除信息的位圖；若待執(zhí)行的是插入操作，則在頭節(jié)點(diǎn)后添加一個(gè)存儲(chǔ)節(jié)點(diǎn)，用于存儲(chǔ)待插入的鍵值信息。（2）若緩沖區(qū)中已存在某節(jié)點(diǎn)，且有關(guān)于該節(jié)點(diǎn)的更新信息出現(xiàn)時(shí)，HNLBI將會(huì)遍歷頭節(jié)點(diǎn)鏈表，找到該節(jié)點(diǎn)，隨后根據(jù)更新操作的類(lèi)型做出相應(yīng)的操作。若為插入操作，則在該節(jié)點(diǎn)所屬的存儲(chǔ)插入操作信息的鏈表尾部創(chuàng)建新的存儲(chǔ)節(jié)點(diǎn)，記錄插入信息；若為刪除操作，則遍歷該節(jié)點(diǎn)所屬的存儲(chǔ)插入操作信息的鏈表，若發(fā)現(xiàn)已存在鍵值相同的冗余存儲(chǔ)節(jié)點(diǎn)，則刪除該冗余節(jié)點(diǎn)，并更新頭節(jié)點(diǎn)中的位圖來(lái)記錄刪除操作信息，若沒(méi)有發(fā)現(xiàn)冗余存儲(chǔ)節(jié)點(diǎn)，則直接更新頭節(jié)點(diǎn)中的位圖即可。（3）HNLBI索引的頭節(jié)點(diǎn)鏈表與每個(gè)節(jié)點(diǎn)所屬的存儲(chǔ)插入信息的鏈表，兩者組合形成一個(gè)頭節(jié)點(diǎn)鏈表。當(dāng)緩沖區(qū)溢出時(shí)，在執(zhí)行替換操作前先遍歷頭節(jié)點(diǎn)鏈表，而后根據(jù)頭節(jié)點(diǎn)信息找出鏈表長(zhǎng)度最大的鏈表進(jìn)行替換。這樣的替換策略可以為緩沖區(qū)提供更多的空余空間，并有效減少了替換操作的執(zhí)行次數(shù)，從而在較大程度上減少了閃存寫(xiě)操作次數(shù)。

1.4 CF-HNLBI

CF-HNLBI（code-first head node list B-tree indexing）是針對(duì)HNLBI緩沖區(qū)替換策略的改進(jìn)。HNLBI緩沖區(qū)替換策略只是簡(jiǎn)單選擇最大長(zhǎng)度的鏈表進(jìn)行替換，并未考慮到節(jié)點(diǎn)的更新頻度。因此，CF-HNLBI設(shè)計(jì)了基于冷熱分區(qū)的替換算法，加入了冷熱分區(qū)的概念，熱區(qū)中存放更新頻繁的節(jié)點(diǎn)數(shù)據(jù)，冷區(qū)中存放更新不頻繁的節(jié)點(diǎn)數(shù)據(jù)。當(dāng)發(fā)生緩沖區(qū)替換時(shí)，CF-HNLBI只選擇冷區(qū)中的節(jié)點(diǎn)進(jìn)行替換。CF-HNLBI為頭節(jié)點(diǎn)設(shè)置冷標(biāo)志位來(lái)反映該頭節(jié)點(diǎn)所對(duì)應(yīng)的B-tree節(jié)點(diǎn)的更新頻度。當(dāng)冷標(biāo)志位為1時(shí)，說(shuō)明該頭節(jié)點(diǎn)為冷節(jié)點(diǎn)，其對(duì)應(yīng)的B-tree節(jié)點(diǎn)更新不頻繁；相反，當(dāng)冷標(biāo)志位為0時(shí)，說(shuō)明該頭節(jié)點(diǎn)為熱節(jié)點(diǎn)，其對(duì)應(yīng)的B-tree節(jié)點(diǎn)更新頻繁。另外，當(dāng)位于緩沖區(qū)中的冷節(jié)點(diǎn)被再次訪問(wèn)時(shí)，則需將此冷節(jié)點(diǎn)標(biāo)記為熱節(jié)點(diǎn)，即將冷標(biāo)識(shí)位設(shè)置為0。

1.5 LU B+tree

LU（lazy update）B+tree將緩沖區(qū)劃分為頁(yè)面緩存區(qū)和延遲更新區(qū)，頁(yè)面緩存區(qū)用來(lái)緩存B+tree的節(jié)點(diǎn)，延遲更新區(qū)用來(lái)緩存節(jié)點(diǎn)的更新請(qǐng)求。當(dāng)有新的更新請(qǐng)求時(shí)，它不是立即提交到B+tree，而是先暫時(shí)存儲(chǔ)在延遲更新池中。當(dāng)有新的更新請(qǐng)求但延遲更新池已滿時(shí)，采用提交策略選擇一組更新請(qǐng)求進(jìn)行提交，從而為新的更新請(qǐng)求留出存儲(chǔ)空間。因此，選擇哪個(gè)組作為提交的組是一個(gè)關(guān)鍵問(wèn)題。

CF-HNLBI設(shè)計(jì)了兩種解決方案：一是最大規(guī)模策略。若新的更新請(qǐng)求在池中有要加入的現(xiàn)有組，就會(huì)發(fā)生命中。由于池的容量是有限的，為了提高命中率，應(yīng)該在池中最大限度地保留更多的小群組，因此該策略選擇容量最大的請(qǐng)求組作為受害者組。這里，組的大小定義為存儲(chǔ)在組中的更新請(qǐng)求的數(shù)量。二是基于成本的策略。與最大規(guī)模策略類(lèi)似，該策略的目標(biāo)是使選擇受害者組的代價(jià)最小化。仿真結(jié)果表明，LU B+tree在保持查詢效率的同時(shí)，顯著提高了傳統(tǒng)B+tree的更新性能。

1.6 MB-tree

MB-tree（modified B-tree）由批處理緩沖區(qū)（batch process buffer，BPB）、根節(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)、葉節(jié)點(diǎn)和葉節(jié)點(diǎn)頭（leaf node header，LNH）組成。BPB存儲(chǔ)在主存中，其他部分存儲(chǔ)在閃存中。MB-tree的結(jié)構(gòu)如圖2所示。

MB-tree設(shè)置批處理緩沖區(qū)（BPB）的目的是減少總的頁(yè)寫(xiě)次數(shù)，以延遲更新。當(dāng)執(zhí)行插入操作時(shí)，若批處理緩沖區(qū)（BPB）未滿，則直接插入條目，直至完全填滿批處理緩沖區(qū)（BPB）；若批處理緩沖區(qū)（BPB）被填滿，BPB將會(huì)根據(jù)每個(gè)條目所屬的葉節(jié)點(diǎn)對(duì)插入的條目進(jìn)行分類(lèi)。接下來(lái)，BPB選擇擁有最多條目的葉節(jié)點(diǎn)，將新條目插入所選的葉節(jié)點(diǎn)。最后，將這個(gè)擁有最多條目的葉節(jié)點(diǎn)寫(xiě)入閃存中。通過(guò)這種方式，MB-tree在處理一組插入操作時(shí)只需執(zhí)行一次寫(xiě)操作。

實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)B-tree和其他B-tree變體相比，MB-tree顯著減少了頁(yè)寫(xiě)次數(shù)，在閃存上的性能表現(xiàn)更好，搜索速度比其他B-tree變體更快。

1.7 HF-tree

HF-tree類(lèi)似于B+tree的結(jié)構(gòu)，其引入了日志結(jié)構(gòu)，以增加一定的讀消耗為代價(jià)來(lái)?yè)Q取低的索引維護(hù)代價(jià)。HF-tree通過(guò)組提交、更新合并以及多級(jí)延遲的方式來(lái)提高更新性能。

HF-tree由BF-tree和Tri-Hash兩部分組成。它的優(yōu)點(diǎn)在于：（1）高速的更新性能，Tri-Hash通過(guò)塊提交和寫(xiě)延遲的方式有效提高索引整體的更新速度；（2）高效的查詢性能，HF-tree通過(guò)Tri-Hash來(lái)查詢最新數(shù)據(jù)，通過(guò)BF-tree來(lái)查詢未修改數(shù)據(jù)，有效提高了索引整體的查詢性能；（3）低垃圾回收成本，HF-tree將更新后的數(shù)據(jù)打包成塊寫(xiě)入閃存中，并且在數(shù)據(jù)移動(dòng)時(shí)也以塊為單位，有效避免了寫(xiě)操作，減少了垃圾數(shù)據(jù)的產(chǎn)生。

其中，BF-tree采取塊存儲(chǔ)模型，根節(jié)點(diǎn)、索引節(jié)點(diǎn)、葉子節(jié)點(diǎn)分別對(duì)應(yīng)存儲(chǔ)在根塊、索引塊、葉子塊中。需要注意的是，葉子塊的前48頁(yè)存儲(chǔ)葉子節(jié)點(diǎn)，后16頁(yè)則用來(lái)存儲(chǔ)葉子節(jié)點(diǎn)的更新。但若一有葉子節(jié)點(diǎn)的更新發(fā)生，就立即寫(xiě)入葉子塊中，會(huì)導(dǎo)致葉子節(jié)點(diǎn)迅速消耗光，因此HF-tree設(shè)計(jì)Tri-Hash來(lái)實(shí)現(xiàn)延遲更新。Tri-Hash結(jié)構(gòu)如圖3所示。

當(dāng)一個(gè)索引項(xiàng)更新時(shí)，會(huì)經(jīng)歷從RAM Hash到Leaf Hash的級(jí)聯(lián)緩沖過(guò)程，最后當(dāng)Leaf Hash滿時(shí)，啟動(dòng)合并操作將Leaf Hash中的更新寫(xiě)入到BF-tree中。這樣，更新被有效地延遲與合并，從而減少額外的寫(xiě)次數(shù)。此外，數(shù)據(jù)的移動(dòng)始終以塊為單位，因此在數(shù)據(jù)移動(dòng)的過(guò)程中，Tri-Hash能夠有效減少垃圾數(shù)據(jù)的產(chǎn)生。

通過(guò)大量和BFTL及IPL的對(duì)比實(shí)驗(yàn)充分說(shuō)明了HF-tree在更新上的卓越性能，同時(shí)在對(duì)等查詢和范圍查詢上也表現(xiàn)出優(yōu)越的性能。

延遲更新類(lèi)索引的主要思想是將更新信息首先保存在緩沖區(qū)內(nèi)，達(dá)到某些條件后再更新到閃存中，以減少閃存的讀寫(xiě)操作。從索引結(jié)構(gòu)上可以分為B-tree及B+tree兩類(lèi)：在以B-tree作為索引結(jié)構(gòu)的優(yōu)化算法中，BFTL在延遲更新的思想上設(shè)計(jì)了節(jié)點(diǎn)轉(zhuǎn)換表來(lái)建立索引單元和節(jié)點(diǎn)的應(yīng)對(duì)關(guān)系。IBSF則以追蹤索引節(jié)點(diǎn)在物理頁(yè)面的寫(xiě)入模式來(lái)替代BFTL的節(jié)點(diǎn)轉(zhuǎn)換表，彌補(bǔ)了BFTL中“內(nèi)存占用量大”及“寫(xiě)入次數(shù)多”的問(wèn)題。HNLBI在處理節(jié)點(diǎn)映射方面引入了“最長(zhǎng)節(jié)點(diǎn)鏈表替換算法”，減少了緩沖區(qū)的空間代價(jià)。而CF-NHLBI在考慮節(jié)點(diǎn)更新的冷熱頻度的基礎(chǔ)上使用“冷熱分區(qū)替換算法”代替HNLBI中的最長(zhǎng)節(jié)點(diǎn)鏈表算法，降低了Btree中節(jié)點(diǎn)的更新頻度。MB-tree使用批處理思想來(lái)處理緩沖區(qū)內(nèi)的條目，保證一組插入操作僅僅在閃存中執(zhí)行一次寫(xiě)操作，從而顯著降低閃存中的寫(xiě)操作。在以B+tree作為索引結(jié)構(gòu)的優(yōu)化算法中，LUB+tree將緩沖區(qū)劃分為頁(yè)面緩存區(qū)和延遲更新區(qū)，并設(shè)計(jì)了兩種提交策略保證查詢效率及更新性能。HF-tree引用了日志結(jié)構(gòu)來(lái)降低索引維護(hù)代價(jià)，這種方式帶來(lái)了優(yōu)秀的更新性能和較快的查詢性能。綜上，延遲更新類(lèi)索引方法除了考慮索引查詢、閃存讀寫(xiě)之類(lèi)的常規(guī)性能指標(biāo)外，還額外考慮了緩沖區(qū)利用率、冷熱均衡等因素，而這類(lèi)因素也是延遲更新類(lèi)索引優(yōu)化的切入點(diǎn)。

2 追加寫(xiě)更新類(lèi)索引

2.1 LSM-tree

LSM-tree又稱日志結(jié)構(gòu)合并樹(shù)（log-structured merge-tree），被用于SSD的日志結(jié)構(gòu)文件系統(tǒng)[51]（源碼：https：//github.com/intfrr/lsmtree）。

LSM-tree的核心思想是利用順序?qū)憗?lái)提高寫(xiě)性能，如圖4所示，它的頂層樹(shù)位于內(nèi)存中，其他層的樹(shù)位于閃存，當(dāng)上層樹(shù)的容量達(dá)到閾值時(shí)，就會(huì)啟動(dòng)歸并算法，上一層向下一層歸并，依次類(lèi)推，直至當(dāng)前層不再溢出。雖然LSM-tree這樣的設(shè)計(jì)會(huì)稍微降低讀性能，但通過(guò)犧牲小部分讀性能換取高性能寫(xiě)，使得LSM-tree成為非常流行的存儲(chǔ)結(jié)構(gòu)。

2.2 FD-tree

FD-tree由香港科技大學(xué)研究團(tuán)隊(duì)提出，是一種使用對(duì)數(shù)方法和分級(jí)級(jí)聯(lián)技術(shù)[52]設(shè)計(jì)的樹(shù)索引（源碼：https：//github.com/Kukos/FDTree---cost-model）。FD-tree由兩部分組成，最頂層是存儲(chǔ)在內(nèi)存中的一個(gè)小的B+tree，叫作Head tree。另一部分是存儲(chǔ)在閃存中的順序排列的多層連續(xù)頁(yè)面，每層能夠容納的數(shù)據(jù)量按對(duì)數(shù)方法組織。FD-tree在相鄰頁(yè)面間插入柵欄，使得查詢時(shí)允許在下一層繼續(xù)搜索，而無(wú)需每次從頭開(kāi)始進(jìn)行掃描或二進(jìn)制搜索。圖5說(shuō)明了FD-tree的結(jié)構(gòu)。

FD-tree的隨機(jī)寫(xiě)操作僅限于小區(qū)域的Head tree中，將大量的隨機(jī)寫(xiě)累積轉(zhuǎn)化成順序?qū)?，?dāng)上層容量滿后，向下一層歸并[53]。FD-tree的歸并操作首先順序讀取相鄰兩層的所有頁(yè)面，然后進(jìn)行歸并，并將歸并后的數(shù)據(jù)寫(xiě)入下一層的頁(yè)面。這樣做不但可以避免大量隨機(jī)寫(xiě)，還能有效減少閃存的擦除次數(shù)，從而提高閃存的壽命。

2.3 CLR-tree

CLR-tree（compact log R-tree）是基于R-tree提出的一種新型索引結(jié)構(gòu)。CLR-tree的設(shè)計(jì)并沒(méi)有改變R-tree的內(nèi)部結(jié)構(gòu)，只是在R-tree的基礎(chǔ)上增加了一個(gè)日志區(qū)域，并針對(duì)加入日志會(huì)導(dǎo)致讀取操作增多的缺陷，設(shè)計(jì)了日志壓縮。所謂日志壓縮就是通過(guò)將屬于某個(gè)節(jié)點(diǎn)的更新操作合并在一起，并將對(duì)于某個(gè)節(jié)點(diǎn)的更新盡量寫(xiě)到一個(gè)頁(yè)中，以減少寫(xiě)次數(shù)。這樣的設(shè)計(jì)使得隨機(jī)寫(xiě)轉(zhuǎn)為順序?qū)?，較大程度地提高了索引的整體性能，并且日志壓縮大大節(jié)約了日志查找時(shí)間。實(shí)驗(yàn)表明CLRtree的性能優(yōu)于現(xiàn)有的方法。

追加寫(xiě)更新類(lèi)索引的主要思想是通過(guò)將大量隨機(jī)寫(xiě)轉(zhuǎn)換為順序?qū)憗?lái)提升性能。LSM-tree設(shè)計(jì)了層次化的數(shù)據(jù)組織結(jié)構(gòu)，并通過(guò)層次間的歸并存放節(jié)點(diǎn)數(shù)據(jù)。FD-tree除了在閃存內(nèi)保存了LSM-tree的層級(jí)結(jié)構(gòu)，還額外設(shè)計(jì)了內(nèi)存中常住的Head tree保存少量隨機(jī)寫(xiě)來(lái)提升性能，并在閃存的層級(jí)結(jié)構(gòu)中設(shè)計(jì)“柵欄”來(lái)提升查詢效率。CLR-tree結(jié)構(gòu)設(shè)計(jì)基于R-tree，并應(yīng)用了日志壓縮技術(shù)來(lái)提升索引性能。綜上，追加寫(xiě)更新類(lèi)索引方法額外考慮了索引結(jié)構(gòu)、查詢效率等因素，而這類(lèi)因素也是追加寫(xiě)更新類(lèi)索引的優(yōu)化方向。

3 自適應(yīng)動(dòng)態(tài)更新類(lèi)索引

3.1 LM-B+tree

LM-B+tree索引結(jié)構(gòu)根據(jù)閃存頁(yè)讀寫(xiě)負(fù)載情況，將索引的緩沖操作邏輯映射于B+tree特定節(jié)點(diǎn)，同時(shí)在系統(tǒng)運(yùn)行過(guò)程中，LM-B+tree根據(jù)索引影響因子的狀況，動(dòng)態(tài)調(diào)整預(yù)存頁(yè)大小及合并時(shí)機(jī)。

LM-B+tree由一棵B+tree和若干個(gè)預(yù)存頁(yè)組成。索引節(jié)點(diǎn)的更新首先根據(jù)頁(yè)面負(fù)載代價(jià)，判定是否更新在預(yù)存頁(yè)中，若要更新在預(yù)存頁(yè)中，檢查預(yù)存頁(yè)是否已滿，如果未滿，就直接寫(xiě)入，如果預(yù)存頁(yè)已滿，迭代更新至下一級(jí)預(yù)存頁(yè)中，直至更新到葉子節(jié)點(diǎn)的父節(jié)點(diǎn)；若更新至緩存頁(yè)將產(chǎn)生較大代價(jià)，則合并更新至B+tree。查詢時(shí)，LM-B+tree首先根據(jù)關(guān)鍵字查找相應(yīng)的預(yù)存頁(yè)。

預(yù)存頁(yè)與日志頁(yè)的不同在于：

（1）數(shù)量上：LM-B+tree根據(jù)B+tree的各個(gè)層節(jié)點(diǎn)讀寫(xiě)的負(fù)載情況，動(dòng)態(tài)劃分預(yù)存頁(yè)對(duì)應(yīng)的節(jié)點(diǎn)數(shù)。

（2）存儲(chǔ)內(nèi)容上：日志頁(yè)僅緩沖了對(duì)索引更新操作的日志記錄，預(yù)存頁(yè)考慮到閃存讀寫(xiě)粒度特性，使用經(jīng)典的最近最少使用（least recently used，LRU）算法，在存儲(chǔ)了更新記錄的同時(shí)存放了經(jīng)常使用的索引記錄，更新記錄具有更高的存儲(chǔ)級(jí)別。

（3）寫(xiě)緩存頁(yè)時(shí)：插入和刪除直接寫(xiě)入預(yù)存頁(yè)，更新若出現(xiàn)范圍跨度時(shí)則需先刪除后寫(xiě)入更新對(duì)應(yīng)的預(yù)存頁(yè)內(nèi)容。

實(shí)驗(yàn)結(jié)果表明，相對(duì)于BFTL等，LM-B+tree的性能更穩(wěn)定。

3.2 FlashDB

FlashDB是一種新型的自適應(yīng)索引技術(shù)，它設(shè)計(jì)了一種代價(jià)估算算法，根據(jù)索引節(jié)點(diǎn)的讀寫(xiě)比例選擇相應(yīng)的更新方式，將工作負(fù)載分為寫(xiě)密集型和讀密集型，寫(xiě)密集型負(fù)載采取日志存儲(chǔ)模式，讀密集型負(fù)載采取磁盤(pán)存儲(chǔ)模式。

FlashDB的日志存儲(chǔ)模式是指，當(dāng)有更新數(shù)據(jù)到達(dá)時(shí)，先將更新數(shù)據(jù)按順序存儲(chǔ)為日志。這樣的設(shè)計(jì)提高了更新速度，但若要讀取一條數(shù)據(jù)記錄時(shí)，必須讀取原始數(shù)據(jù)信息和存儲(chǔ)在日志中的更新數(shù)據(jù)這兩部分內(nèi)容。因此，日志存儲(chǔ)模式不適合讀密集型的工作負(fù)載。

FlashDB的磁盤(pán)存儲(chǔ)模式是指直接將索引當(dāng)成數(shù)據(jù)存盤(pán)。因?yàn)殚W存的讀寫(xiě)速度不均衡，隨機(jī)訪問(wèn)性能很好，訪問(wèn)索引時(shí)基本不會(huì)有延遲，但若更新操作繁多，閃存寫(xiě)的速度就會(huì)很慢，所以磁盤(pán)存儲(chǔ)模式很適合讀密集型負(fù)載。

3.3 LA-tree

LA（lazy adaptive）-tree是一種新型索引結(jié)構(gòu)，采用以下兩種技術(shù)：（1）級(jí)聯(lián)緩沖，LA-tree將多個(gè)層的節(jié)點(diǎn)存入緩沖區(qū)中，緩沖區(qū)中保存了對(duì)這層節(jié)點(diǎn)及其孩子節(jié)點(diǎn)的更新操作。（2）一種在線自適應(yīng)算法，LA-tree索引使用最優(yōu)在線算法動(dòng)態(tài)適應(yīng)任意工作負(fù)載[54-55]，從而為更新和查找提供有效支持?；谏鲜鲈O(shè)計(jì)，使LA-tree索引在查詢密集和更新密集的訪問(wèn)模式下都有較高效率。

3.4 DB-tree

DB-tree索引將更新操作以“偽B+tree”的結(jié)構(gòu)形式存儲(chǔ)，從而避免檢索時(shí)掃描整個(gè)更新日志區(qū)；以分支合并的方式使更新操作有針對(duì)性地聚集于閃存頁(yè)；引入更新緩沖區(qū)大小及合并頻率的自適應(yīng)機(jī)制使閃存數(shù)據(jù)庫(kù)適用于不同的讀寫(xiě)負(fù)載。

DB-tree由OB-tree和NB-tree兩部分組成，其中OBtree是一棵傳統(tǒng)的B+tree，NB-tree為一棵“偽B+tree”。DB-tree純閃存，無(wú)日志，能夠根據(jù)閃存負(fù)載情況，自適應(yīng)調(diào)整緩沖區(qū)大小及合并操作?！皞蜝+tree”的設(shè)計(jì)使得DB-tree在執(zhí)行檢索操作時(shí)無(wú)需掃描整個(gè)緩沖區(qū)。因此，DB-tree減少了重新調(diào)整索引的次數(shù)以及合并操作的代價(jià)，加快了更新檢索速度，提高了索引的整體性能。

自適應(yīng)動(dòng)態(tài)更新類(lèi)索引的主要思想是根據(jù)不同的讀寫(xiě)特征采取相應(yīng)的索引策略來(lái)提升索引性能。LMB+tree提出了預(yù)存頁(yè)的設(shè)計(jì)，用來(lái)保存索引更新的操作日志，并根據(jù)負(fù)載情況動(dòng)態(tài)劃分節(jié)點(diǎn)對(duì)應(yīng)的預(yù)存頁(yè)。DB-tree在緩沖區(qū)內(nèi)針對(duì)大小及合并頻率引入動(dòng)態(tài)更新機(jī)制，使其閃存數(shù)據(jù)庫(kù)可以適應(yīng)多種類(lèi)型負(fù)載。FLSHDB中索引節(jié)點(diǎn)的更新方式取決于負(fù)載的讀寫(xiě)比例，其中日志更新模式可以有效提升更新速度，而磁盤(pán)更新模式適合讀密集型負(fù)載。LA-tree借鑒了最佳寫(xiě)更新類(lèi)索引的多層級(jí)模式，并應(yīng)用了最優(yōu)在線算法來(lái)動(dòng)態(tài)適應(yīng)工作負(fù)載。綜上，自適應(yīng)動(dòng)態(tài)更新類(lèi)索引的優(yōu)化更關(guān)注索引結(jié)構(gòu)及自適應(yīng)的索引策略設(shè)計(jì)。

4 討論

本章主要討論各種索引算法本身的優(yōu)缺點(diǎn)和橫向之間的對(duì)比結(jié)果。表2為對(duì)比表格中符號(hào)的具體解釋，表3和表4對(duì)論文中羅列的索引進(jìn)行了比較，其中“—”表示在論文中沒(méi)有明確說(shuō)明。以上索引僅在某幾個(gè)方面優(yōu)化了索引性能，并未全面考慮到其他影響因素?？梢钥闯觯?/p>

表2 符號(hào)含義Table 2 Symbol meaning

表3 索引優(yōu)缺點(diǎn)總結(jié)Table 3 Summary on advantages and disadvantages of index

（1）每種索引各有優(yōu)缺點(diǎn)，因此，如何針對(duì)各個(gè)索引做到揚(yáng)長(zhǎng)避短，最大限度地規(guī)避劣勢(shì)，利用優(yōu)勢(shì)，是接下來(lái)研究的可行方向。

（2）表4中，IBSF相較于BFTL，更新性能、查詢性能以及空間復(fù)雜度都有較大提升。BFTL通過(guò)將節(jié)點(diǎn)分散到多個(gè)頁(yè)面來(lái)交換讀和寫(xiě)，并且由于維護(hù)的輔助信息，它還會(huì)增加主內(nèi)存和輔助內(nèi)存開(kāi)銷(xiāo)，BFTL慢慢已不再適用于當(dāng)代SSD。IBSF試圖通過(guò)節(jié)點(diǎn)轉(zhuǎn)換表來(lái)延遲緩沖區(qū)溢出，然而它的性能仍然嚴(yán)重依賴于主存。

（3）表4中，IBSF和CF-HNLBI執(zhí)行一次插入的讀代價(jià)相同，這是因?yàn)閮烧咴诿恳粚佣夹枳x取一個(gè)閃存頁(yè)來(lái)獲得該層某個(gè)B-tree節(jié)點(diǎn)的信息。另外，CF-HNLBI索引的閃存讀代價(jià)與IBSF索引相同，均優(yōu)于BFTL。

表4 索引性能對(duì)比Table 4 Index performance comparison

（4）LU B+tree的核心思想是通過(guò)將緩存區(qū)分區(qū)與組提交方式來(lái)控制寫(xiě)和讀，然而這可能導(dǎo)致CPU和I/O代價(jià)較高。MB-tree設(shè)置批處理緩沖區(qū)以延遲樹(shù)的更新重建，但需額外的輔助葉節(jié)點(diǎn)，因此需要額外的CPU和I/O操作來(lái)進(jìn)行搜索和維護(hù)。

（5）FD-tree由于高度的增加，它的搜索時(shí)間可能比B-tree的搜索時(shí)間要差。此外，過(guò)多的寫(xiě)操作會(huì)損害SSD的壽命。

（6）LA-tree由于插入/刪除操作都是通過(guò)重復(fù)的緩沖區(qū)清空和寫(xiě)入來(lái)實(shí)現(xiàn)的，寫(xiě)放大和讀增加是不可避免的，對(duì)應(yīng)操作的時(shí)間自然也較長(zhǎng)。

5 研究展望

閃存由于卓越的I/O性能[56]，以及低功耗、高抗振等特點(diǎn)，在存儲(chǔ)領(lǐng)域發(fā)展飛速，被廣泛認(rèn)為是能夠代替磁盤(pán)的新一代存儲(chǔ)介質(zhì)之一[57]。但傳統(tǒng)磁盤(pán)索引無(wú)法適應(yīng)閃存的特性。因此，基于傳統(tǒng)磁盤(pán)索引的改進(jìn)和優(yōu)化，設(shè)計(jì)適配閃存的索引技術(shù)是關(guān)鍵，對(duì)不同類(lèi)型閃存索引的研究至關(guān)重要。本文從索引更新策略角度出發(fā)，分別介紹了各類(lèi)閃存索引，分析對(duì)比了各自的優(yōu)劣勢(shì)，發(fā)現(xiàn)現(xiàn)有閃存索引研究的一些技術(shù)瓶頸問(wèn)題仍需深入研究，這些研究可以從以下幾個(gè)方面展開(kāi)：

（1）基于深度強(qiáng)化學(xué)習(xí)的索引優(yōu)化

目前多數(shù)研究已經(jīng)基本解決了索引在本地事務(wù)處理過(guò)程中效率方面的問(wèn)題，但在云環(huán)境中，傳統(tǒng)的索引方法很難應(yīng)付數(shù)以百萬(wàn)計(jì)的數(shù)據(jù)庫(kù)實(shí)例。傳統(tǒng)的機(jī)器學(xué)習(xí)模型只能描述一個(gè)層次的學(xué)習(xí)過(guò)程，過(guò)于簡(jiǎn)單，難以求解海量數(shù)據(jù)索引的復(fù)雜問(wèn)題。深度強(qiáng)化學(xué)習(xí)（deep reinforcement learning，DRL）將深度學(xué)習(xí)與強(qiáng)化學(xué)習(xí)結(jié)合，并利用其搜索強(qiáng)大解空間的能力來(lái)解決NP難問(wèn)題，深度強(qiáng)化學(xué)習(xí)雖然對(duì)樣本量需求減少，但訓(xùn)練時(shí)間較長(zhǎng)，難以適應(yīng)高強(qiáng)度的在線數(shù)據(jù)處理需求。隨著大規(guī)模數(shù)據(jù)管理系統(tǒng)的應(yīng)用，如何高效充分地利用深度強(qiáng)化學(xué)習(xí)方法來(lái)優(yōu)化索引的更新，提升索引的性能將成為未來(lái)的研究趨勢(shì)。

（2）面向海量流數(shù)據(jù)的分布式索引

隨著Storm[58]、Flink[59]等高吞吐的分布式流計(jì)算平臺(tái)大量涌現(xiàn)，海量流數(shù)據(jù)的處理與分析越來(lái)越受到人們的關(guān)注，但目前數(shù)據(jù)流的處理仍然依賴實(shí)時(shí)存儲(chǔ)，流數(shù)據(jù)處理框架在存儲(chǔ)層面只保存查詢和計(jì)算結(jié)果，不存儲(chǔ)完整數(shù)據(jù)流。海量流數(shù)據(jù)實(shí)時(shí)存儲(chǔ)的一個(gè)關(guān)鍵挑戰(zhàn)是在不影響讀寫(xiě)性能的前提下高效實(shí)時(shí)地構(gòu)建索引，以實(shí)現(xiàn)快速查詢?，F(xiàn)有的分布式索引可以分為主從式結(jié)構(gòu)[60-61]和對(duì)等結(jié)構(gòu)[62-63]，在數(shù)據(jù)實(shí)時(shí)性、索引平衡性及系統(tǒng)性能方面存在一定缺陷。大數(shù)據(jù)流場(chǎng)景下，索引的更新頻率高，存儲(chǔ)開(kāi)銷(xiāo)大，如何在保證大規(guī)模存儲(chǔ)系統(tǒng)性能的前提下，設(shè)計(jì)體量大、維度多、吞吐量高的流數(shù)據(jù)索引方法將成為未來(lái)的研究熱點(diǎn)之一。

（3）面向新型非易失存儲(chǔ)器的索引優(yōu)化

伴隨著新型存儲(chǔ)介質(zhì)的商用及存儲(chǔ)架構(gòu)的發(fā)展，當(dāng)前索引技術(shù)將部署和應(yīng)用到以非易失性存儲(chǔ)器（nonvolatile memory，NVM）[64]為代表的、具有非易失、低延遲、高隨機(jī)讀寫(xiě)能力的新型混合硬件平臺(tái)上，如何在此類(lèi)環(huán)境下構(gòu)建高效索引系統(tǒng)也將成為研究趨勢(shì)。近兩年的研究工作大多基于英特爾傲騰持久內(nèi)存[65-66]，并且針對(duì)過(guò)去基于DRAM模擬研究工作的問(wèn)題，對(duì)傲騰持久內(nèi)存的一些硬件特性進(jìn)行了適配。但英特爾尚未公布傲騰持久內(nèi)存的內(nèi)部原理和架構(gòu)，給相關(guān)的存儲(chǔ)優(yōu)化工作帶來(lái)阻礙。

綜上所述，在飛速發(fā)展的大數(shù)據(jù)時(shí)代，對(duì)閃存索引技術(shù)的研究仍任重而道遠(yuǎn)。思考如何在基于深度強(qiáng)化學(xué)習(xí)的索引優(yōu)化、面向海量流數(shù)據(jù)的分布式索引優(yōu)化以及面向新型非易失存儲(chǔ)器的索引優(yōu)化等方面取得突破性進(jìn)展，將是未來(lái)的主要工作之一。

6 結(jié)束語(yǔ)

本文對(duì)面向閃存的樹(shù)型索引研究現(xiàn)狀進(jìn)行了綜述。首先對(duì)背景知識(shí)和研究問(wèn)題進(jìn)行了介紹，給出了樹(shù)型索引更新策略面臨的挑戰(zhàn)，然后對(duì)現(xiàn)有的索引方法進(jìn)行分類(lèi)介紹，從索引的更新方式出發(fā)，根據(jù)類(lèi)別分析總結(jié)了目前部分樹(shù)型閃存索引的優(yōu)勢(shì)和缺陷，并提出未來(lái)閃存索引研究的一些方向和思考。

傳統(tǒng)磁盤(pán)索引無(wú)法適應(yīng)閃存的特性，因此，基于傳統(tǒng)磁盤(pán)索引的改進(jìn)和優(yōu)化，使得索引能夠適用于閃存設(shè)備，極大提高了存儲(chǔ)速度，為大數(shù)據(jù)存儲(chǔ)領(lǐng)域帶來(lái)新突破。隨著各類(lèi)大數(shù)據(jù)存儲(chǔ)技術(shù)研究的不斷深入，閃存索引技術(shù)必須不斷創(chuàng)新，適應(yīng)直至融合于新的大數(shù)據(jù)發(fā)展潮流。