孫 鑒，武曉曉，謝開斌，高錦濤，劉凇佐，巫思敏

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

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

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

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

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

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

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

閃存具有以下幾個顯著特點：

（1）讀寫速度不對稱：閃存寫操作的總體訪問延遲比讀操作的總體訪問延遲要高很多。一般來說，閃存寫延遲比讀延遲高一個數(shù)量級[5]。

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

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

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

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

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

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

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

表1 索引分類Table 1 Index classification

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

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

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

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

1 延遲更新類索引

1.1 BFTL

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

1.2 IBSF

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

1.3 HNLBI

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

1.4 CF-HNLBI

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

1.5 LU B+tree

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

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

1.6 MB-tree

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

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

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

1.7 HF-tree

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

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

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

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

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

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

2 追加寫更新類索引

2.1 LSM-tree

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

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

2.2 FD-tree

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

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

2.3 CLR-tree

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

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

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

3.1 LM-B+tree

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

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

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

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

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

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

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

3.2 FlashDB

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

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

FlashDB的磁盤存儲模式是指直接將索引當(dāng)成數(shù)據(jù)存盤。因為閃存的讀寫速度不均衡，隨機訪問性能很好，訪問索引時基本不會有延遲，但若更新操作繁多，閃存寫的速度就會很慢，所以磁盤存儲模式很適合讀密集型負載。

3.3 LA-tree

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

3.4 DB-tree

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

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

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

4 討論

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

表2 符號含義Table 2 Symbol meaning

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

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

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

（3）表4中，IBSF和CF-HNLBI執(zhí)行一次插入的讀代價相同，這是因為兩者在每一層都需讀取一個閃存頁來獲得該層某個B-tree節(jié)點的信息。另外，CF-HNLBI索引的閃存讀代價與IBSF索引相同，均優(yōu)于BFTL。

表4 索引性能對比Table 4 Index performance comparison

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

（5）FD-tree由于高度的增加，它的搜索時間可能比B-tree的搜索時間要差。此外，過多的寫操作會損害SSD的壽命。

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

5 研究展望

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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