基于內存的HBase二級索引設計

崔 晨，鄭林江，韓鳳萍，何牧君

(1.重慶大學計算機學院，重慶400044; 2.重慶城市綜合交通樞紐開發(fā)投資有限公司，重慶401121)(*通信作者電子郵箱15123034669@163.com)

0 引言

物聯(lián)網和大數(shù)據(jù)的廣泛應用，產生了海量的多類型實時數(shù)據(jù)。傳統(tǒng)的數(shù)據(jù)存儲與管理方法已難以適應當前大規(guī)模數(shù)據(jù)管理對效率的需求，因此非關系型數(shù)據(jù)庫(Not Only SQL，NoSQL)［1］得以迅速發(fā)展。HBase作為NoSQL數(shù)據(jù)庫的代表，已被廣泛應用于各行各業(yè)的數(shù)據(jù)存儲與管理中。索引是數(shù)據(jù)庫中提高數(shù)據(jù)管理與查詢效率的關鍵技術，HBase在行鍵(Rowkey)上建立了類B+樹索引，可以高效地支持基于行鍵的快速數(shù)據(jù)查詢［2］，但對非行鍵的列沒有建立索引，故進行非行鍵的列的查詢時，需要對全表進行掃描，這樣的查詢效率十分低下，極大限制了HBase在復雜條件下的查詢性能。為解決這一問題，現(xiàn)有研究提出建立非行鍵的列與行鍵的索引，從而構建起二級索引方案，方案在對非行鍵的列進行查詢時，先通過二級索引獲取與其對應的行鍵，再通過行鍵到HBase中進行查找。

目前，國內部分企業(yè)和個人基于第三方開源軟件進行索引設計，使用搜索服務器Solr［3］來構建HBase二級索引。Solr是一個基于Lucene［4］的企業(yè)級全文搜索服務器，用戶可以通過超文本傳輸協(xié)議(HyperText Transfer Protocol，HTTP)請求向Solr提交HBase中的數(shù)據(jù)，建立非行鍵的列與行鍵的映射，生成索引;也可以通過HTTP Get操作提出查找請求返回索引中的行鍵。華為基于協(xié)處理器(Coprocessors)進行了HBase二級索引的實現(xiàn)，它利用HBase的原生代碼即可獲得索引，但這也帶來插入數(shù)據(jù)速度變慢、升級維護困難以及索引無法動態(tài)修改等問題。葛微等［2］提出了名為HiBase的二級索引，它是一種基于分層式索引的設計方案，其將熱點索引進行緩存，并建立高效的緩存替換策略來提高二級索引的查詢速度。Zou等［5］提出了互補聚簇式索引(Complemental Clustering Index，CCIndex)，該方案把數(shù)據(jù)的詳細信息也存放在索引表中，不需要通過獲取的行鍵再到原表中去查找數(shù)據(jù)。

在索引實現(xiàn)方面，基于內存的索引相較于傳統(tǒng)位于磁盤的索引在設計和架構上都大不相同，基于內存的索引在查詢效率上得到了極大提升。廣泛采用的內存索引有T樹［6］、基于緩存敏感的CSS/CSB+樹和改進的Hash索引等。T樹，是針對B+樹在內存中空間浪費的問題而提出的一種樹型索引。T樹所有節(jié)點都直接指引數(shù)據(jù)項，節(jié)省了中間節(jié)點所占空間。而針對Hash索引空間利用問題，提出了最小完美Hash索引［7］，其哈希函數(shù)不會產生沖突且函數(shù)的值域和參數(shù)域的大小完全相等，但這一哈希函數(shù)構造難度非常大。后來，研究發(fā)現(xiàn)CPU高速緩存對數(shù)據(jù)查詢性能有著非常顯著的影響［8］，所以研究者在B+樹的基礎上對緩存作了優(yōu)化，提出了CSB+樹［9］。在Hash索引的基礎上，提出了可擴展Hash、桶鏈Hash等緩存敏感的索引結構。到了2007年，Ross［10］提出了基于現(xiàn)代處理器的Hash預取算法，將單指令多數(shù)據(jù)流(Single Instruction Multiple Data，SIMD)指令集融入到 Hash算法中，在內存環(huán)境中大大提高了索引的性能。文獻［11］基于有界障礙(Bounded Disorder，BD)方法提出了一種BD樹索引，其將樹形結構與Hash表結構結合，上層是樹結構，下層葉子節(jié)點是哈希表，每個哈希表中桶的大小等于CPU緩存塊的大小。這樣的索引結構既對緩存作了優(yōu)化，又實現(xiàn)了針對Hash表的范圍查找。文獻［12］中根據(jù)BD樹索引的思想，實現(xiàn)了B+樹索引與Hash索引的結合并進行了實驗，結果展現(xiàn)BD樹索引具有較好的性能。

本文提出一種基于內存的HBase二級索引的設計方案。為HBase中非行鍵的列建立索引并存儲在Spark集群中。Spark是一款基于內存的并行計算框架［13］，其將數(shù)據(jù)加載到內存中，然后在內存中完成計算，且Spark集群能構造一個大的內存環(huán)境。由于是將索引建立在內存中，所以在索引的選擇上希望得到節(jié)約存儲空間、查詢效率較高的索引。本文根據(jù)要建索引的列的基數(shù)大小以及是否涉及范圍查詢構建了三種基于內存的索引，分別是位圖索引、分段Hash索引以及BD森林索引，并利用Spark并行化的特點來提高索引的查詢效率。

1 基于內存的HBase二級索引總體設計

1.1 二級索引結構

HBase對行鍵建立了索引，對非行鍵的列未建立索引，這嚴重影響了條件查詢的效率。為此，針對HBase在進行非行鍵的列的查詢和組合條件查詢時效率較低的問題，本文對需要查詢的列建立與行鍵對應的二級索引，建立的二級索引結構如圖1所示。圖1中對HBase的簇(Column Family，CF)的NAME列和ADDR.列在Spark上建立了非行鍵的列的索引，索引可以通過 NAME列或 ADDR.列中的屬性值映射到HBase中對應的行鍵。有時會對NAME列與ADDR.列進行組合條件查詢，故針對這兩列建立了組合條件的索引，可以通過索引映射到滿足這一組合條件的行鍵。

圖1 HBase二級索引結構Fig.1 Secondary index structure in HBase

查詢非行鍵的列或組合條件時，可以先通過位于Spark內存環(huán)境中的索引獲取對應的行鍵，再利用行鍵在HBase中查詢符合條件的記錄。這樣的二級索引能極大提高條件查詢的效率。

1.2 二級索引查詢框架

面對非行鍵的列或組合條件的查詢，可以先建立上述結構的二級索引。該索引以彈性分布式數(shù)據(jù)集(Resilient Distributed Dataset，RDD)的形式存儲在Spark的內存環(huán)境中，RDD是Spark內存計算中一種彈性分布式數(shù)據(jù)集，且在Spark上有許多內置操作，可以將其并行化地轉換。為了防止斷電內存數(shù)據(jù)的丟失，對主要的RDD進行磁盤持久化，也可從磁盤中讀取歷史數(shù)據(jù)的RDD。查詢時在Spark中對索引的RDD進行操作，獲取對應的行鍵，再用行鍵在HBase中查找對應的記錄并返回給查詢的客戶端。圖2展示了二級索引的查詢框架。

圖2 二級索引查詢框架Fig.2 Secondary index query framework

這樣的查詢框架可以充分發(fā)揮HBase中行鍵的作用，同時利用了Spark內存計算和并行化的優(yōu)勢。為了提高框架的查詢效率，本文要構建合適的內存索引用于該查詢框架中，這將在第2章節(jié)具體討論。

1.3 表和二級索引的構造

使用上述的二級索引，首先要在HBase中構造存儲數(shù)據(jù)的表，其中行鍵設計是構造表的關鍵。由于HBase是無模式的，事先不需要定義列限定符和數(shù)據(jù)類型，只需利用數(shù)據(jù)中的相關字段構建每條數(shù)據(jù)的行鍵。在構建行鍵時，要選擇反映數(shù)據(jù)重要特征的字段組合成行鍵，并且這樣的行鍵要具有唯一性。例如在后面的實驗中針對基于射頻識別(Radio Frequency IDentification，RFID)的機動車電子車牌數(shù)據(jù)，本文選擇采集點IP和通行時間這兩個重要的字段來建立行鍵，同時在其基礎上加入隨機數(shù)，使行鍵更加唯一和分散，避免熱點問題。如果行鍵過長，為了在讀寫以及存儲時具有好的性能，可以對行鍵進行壓縮處理。

在二級索引的構造過程中，建立一個輔助的記錄表。對HBase表中新插入的數(shù)據(jù)存儲到輔助的記錄表中，每當記錄表中的數(shù)據(jù)個數(shù)達到一定的閾值時，就對記錄表中的數(shù)據(jù)建立對應的索引并以RDD的形式存儲(具體的索引構建過程見第二章)，故所建的索引都是分段的索引，這樣有利于Spark的并行操作。與此同時清空輔助的記錄表，用于記錄下一批新插入的數(shù)據(jù)，從而對這部分新的數(shù)據(jù)建立二級索引。由于HBase中更新操作實際上是插入新的數(shù)據(jù)，而本文在行鍵的構造中加入隨機數(shù)使其唯一化，不存在行鍵相同根據(jù)時間戳來更新數(shù)據(jù)的情況，故本文中二級索引不進行更新。當在HBase的表中刪除數(shù)據(jù)時，則要將RDD形式的索引全部刪除，重新分批讀取HBase中的數(shù)據(jù)，每讀取一定數(shù)量的數(shù)據(jù)就建立分段的索引，以保證索引內容的正確性。

2 內存索引構建

列的基數(shù)是指該列擁有的不重復數(shù)值的個數(shù)。例如:員工信息表中性別這列的基數(shù)是2，只有“男”和“女”兩個值。列的基數(shù)的大小直接影響索引的選擇與構造。同時，是否涉及范圍查詢也決定了索引方法的選擇。為此，根據(jù)各列基數(shù)大小以及是否涉及范圍查詢，本文構建了不同的內存索引。針對基數(shù)較小列，構建位圖索引;針對基數(shù)較大但不涉及范圍查詢的列，構建分段Hash索引;針對基數(shù)較大且涉及范圍查詢的列，構建BD森林索引。整個索引構建的步驟流程如圖3所示。

2.1 對基數(shù)較小列的索引

一般認為列基數(shù)小于100且小于HBase中的總列數(shù)的0.1%時，該列即為基數(shù)較小列。針對基數(shù)較小列，由于字段重復值較多，建立樹形索引不能帶來快速的查詢響應，還會帶來索引空間冗余，達不到“空間換取時間”的目的。因此，針對基數(shù)較小列，采用位圖索引進行二級索引的構建。

位圖索引是用二進制位0、1組成的位向量表示數(shù)據(jù)的索引信息，并通過將檢索條件映射為二進制位的邏輯運算來實現(xiàn)高效的查詢。設有一組數(shù)據(jù)，數(shù)據(jù)的總記錄數(shù)為N，數(shù)據(jù)中有一列為基數(shù)較小列。對基數(shù)較小列建立索引，針對基數(shù)較小列的每一屬性值a建立一個位向量X，X的長度為N，判斷X的第j位Xj表示第j條記錄在該列中的值是否為屬性值a，若是a，則Xj=1;若不是a，則Xj=0。員工信息表中性別這一列建立的位圖索引示例如圖4所示。

圖3 索引構建步驟流程Fig.3 Flowchart of index building step

圖4 員工信息表的性別位圖索引Fig.4 Bitmap index of employee information about sex

位圖索引采用0、1來存儲信息，在內存中所占空間很小。內存中一個字節(jié)的空間可以存儲8條某個屬性值的取值情況，例如800萬條員工信息對性別為“男”的情況建立索引，則只需消耗不到1 MB內存空間。位圖索引的另一優(yōu)勢就是可以將組合查詢轉為高性能的位運算。例如已經得到N條記錄其A列中屬性值a的位向量X和B列中屬性值b的位向量W。若要查詢的組合條件為A列中值為a且B列中值為b的記錄時，只需將X與W進行按位與的運算得到位向量Z，若Zj=1，則第j條記錄符合本文的查詢條件。

在本文中，用字節(jié)數(shù)組來存儲位圖索引并將其建立在Spark構成的內存空間中。為了方便構造和提高構造速度，取每N條記錄為一組構建分段的位圖索引。每段位圖索引在Spark內存中用parallelize方法轉為RDD形式，RDD在Spark的環(huán)境中可以被緩存且支持并行操作。為了防止斷電內存數(shù)據(jù)丟失，將這些RDD進行RDD.saveAsObjectFile執(zhí)行操作，從而把數(shù)據(jù)持久化到硬盤中。在查詢時，由于需要利用數(shù)組下標和數(shù)組中字節(jié)數(shù)值轉為對應記錄的取值情況，故將這些分段的位圖索引按記錄順序進行整合，用Spark中RDD.collect執(zhí)行操作轉為一個整體的位于本地的有序數(shù)組。對位圖索引進行查詢就是對這一內存中的數(shù)組進行遍歷，內存中連續(xù)空間遍歷的速度我們是可以接受的，故針對基數(shù)較少的列建立位圖索引是有效的。位圖索引在Spark中的操作如圖5所示。

圖5 位圖索引在Spark中操作過程Fig.5 Operation process of bitmap index in Spark

2.2 對基數(shù)較大但不涉及范圍查詢的列的索引

當HBase中某列的基數(shù)較大時，就可以使用Hash索引或樹形索引。當該列不涉及范圍查詢時，即根據(jù)一個確定的值進行等值查詢，選擇能在O(1)的時間復雜度下準確查找的Hash索引。

本文中對基數(shù)較大但不涉及范圍查詢的列構建鏈接桶哈希，其結構如圖6所示。在構建Hash索引時，仍將數(shù)據(jù)分段，建立分段Hash索引，這樣不僅能方便后面的并行化查找，同時可以根據(jù)分段的大小事先確定桶的數(shù)目，以防桶的數(shù)目過小帶來查詢效率下降以及桶的數(shù)目過大帶來空間浪費的問題。為了減少哈希表所占用的內存空間，提高負載因子，通常的負載因子為0.75，這里選用0.8，即要對 N條數(shù)據(jù)建立Hash索引，則先產生桶的數(shù)目為1.25*N的哈希表。雖然提高負載因子會增加桶中鏈的長度從而增加查詢數(shù)據(jù)的時間開銷，但這是時間成本和空間成本上的一種折中，是可以接受的。

圖6 鏈接桶哈希結構Fig.6 Hash structure of link bucket

在查詢時，對分段Hash索引進行并行的查找［14］，這些索引轉為RDD的形式存儲在內存中，在硬盤上也有備份。利用Spark中RDD.map轉化操作算子對每個分段Hash索引進行時間復雜度為O(1)的快速查找。這樣的查詢速度非常理想，不會因數(shù)據(jù)量的增大產生巨大變化，這也是本文愿意提高負載因子的原因。索引在Spark中的操作如圖7所示。

圖7 分段哈希索引在Spark中操作過程Fig.7 Operation process of segmented hash index in Spark

2.3 對基數(shù)較大且涉及范圍查詢的列的索引

2.3.1 BD 樹索引的結構

Hash索引不能進行范圍查詢，故面對HBase中某列基數(shù)較大且涉及范圍查詢時，本文采用BD樹索引的思想，構建由多棵BD樹索引組成的BD森林索引。其中BD樹索引由B+樹與哈希表結合得到，即索引的樹結構是B+樹，B+樹的葉子節(jié)點由n個哈希桶組成，且每個哈希桶的大小等于CPU緩存塊的大小，故哈希桶中存放數(shù)據(jù)是固定的。同時為了能進行范圍查找，各葉子節(jié)點按順序連接起來，可以通過指針進行查詢。圖8是BD樹索引的結構。

圖8 BD樹索引結構Fig.8 Index structure of BD tree

在構造BD樹索引時，使用遞歸的方法將關鍵字不斷插入。先查找關鍵字所在的哈希表，然后定位到其所在的桶中，若桶未滿則插入關鍵字;若桶已滿則需分裂該節(jié)點，將原哈希表中所有關鍵字分配到兩個新的哈希表中，分界可選原哈希表關鍵字的最大值和最小值的均值，同時對上層B+樹進行修改，產生指向新的哈希表節(jié)點的指針。詳細過程可以參考文獻［11－12］。

在BD樹索引的查詢中，面對精確查詢，根據(jù)關鍵字在B+樹中找到對應的葉子節(jié)點，即哈希表，接著則是在哈希表中進行查詢。BD樹索引關鍵在于可以進行范圍查詢，當查詢的關鍵字范圍為［ks，ke］時，找到關鍵字ks所在的哈希表記為U，找到關鍵字ke所在的哈希表記為V，則U、V之間的哈希表的所有值(哈希表按順序用指針串聯(lián)在一起)、U中關鍵字大于ks對應的值和V中關鍵字小于ke對應的值是范圍查詢的結果。

2.3.2 BD 森樹索引的結構

本文對基數(shù)較大且涉及范圍查詢的列構建BD森林索引，即多棵BD樹索引，其結構如圖9所示。

仍然將數(shù)據(jù)分段，對每一段建立BD樹索引，并轉為RDD的形式存儲在內存中，利用Spark中操作對每個BD樹索引進行查詢，操作過程同圖7的分段Hash索引。但這樣在面對范圍查詢時，要對每棵BD樹進行查詢，最后將查詢結果進行匯總，算法1描述了BD森林索引范圍查詢算法的過程。

算法1 BD森林索引范圍查詢算法。

輸入 查詢范圍［ks，ke］的關鍵字 ks，ke。

輸出 行鍵集合RQ。

RQ← //結果集合設為空

for each tree T in Tsdo //遍歷每棵BD樹索引

Hs← T.GetHash(ks) //通過樹形索引查找ks所在的哈希表

He← T.GetHash(ke)

H←Hs

while next［H］≠ Hsdo

H ← next［H］

RQ∪allValue［H］ //將哈希表中所有值并入結果集合中

end while

for each map M in Hsdo //遍歷哈希表

if key［M］ ＞ ksthen

//當遍歷映射的鍵大于范圍開始的關鍵字時

RQ∪value［M］ //將映射的值并入結果集合中

end if

end for

for each map M in Hedo

if key［M］ ＜ kethen//當遍歷映射的鍵小于范圍結束的關鍵字時

RQ ∪ value［M］

end if

end for

end for

構建BD森林索引是因為一次性將所有數(shù)據(jù)構造成BD樹索引，在轉化RDD時會因為樹的遞歸構造次數(shù)［15］太多帶來StackOverflowError問題，無法轉為RDD存儲在Spark內存環(huán)境中。構建BD森林索引，降低每棵樹的高度，減少樹的遞歸構造深度，將其成功轉為RDD。范圍查詢時雖然要對森林中的每棵樹進行操作，但可以利用Spark中 RDD.map轉化操作算子進行并行操作，故效果是可以接受的。

3 實驗與結果分析

圖9 BD森林索引結構Fig.9 Index structure of BD forest

3.1 實驗環(huán)境與數(shù)據(jù)

本文的實驗環(huán)境是在三臺虛擬機下搭建的HBase集群與Spark集群，為了進行對比實驗還搭建了Solr集群。每臺虛擬機的環(huán)境是1核CPU，2 GB內存，60 GB硬盤，操作系統(tǒng)是CentOS7。

本文的實驗數(shù)據(jù)是基于RFID電子車牌的交通數(shù)據(jù)，其來源于重慶市智能交通系統(tǒng)，其數(shù)據(jù)模型如表1所示。數(shù)據(jù)模型中各字段的含義分別是:記錄在表中的id號、采集點名稱、行駛方向、采集點的IP標識、車輛的電子車牌號、車輛通過時間、車輛類型、號牌的種類以及車輛使用性質。數(shù)據(jù)存入HBase中，用01到99之間的隨機數(shù)加上采集點IP標識加上通行時間的月日時分秒構成每條原始記錄的行鍵(Rowkey)，例如表1中的第一條記錄的行鍵為“19101112010229012445”(產生的隨機數(shù)是19)。這樣的行鍵具有唯一性和分散性。

在后面的實驗中，主要對三種索引的檢索效率進行了實驗對比，期望基于這樣的二級索引能在數(shù)據(jù)查詢上帶來效率的提高。另外對索引的大小也十分關注，期望索引所占空間合理，以便能在內存中存儲，故在實驗中對索引所占的空間大小也進行了實驗測試。

表1 原始數(shù)據(jù)模型Tab.1 Original data model

3.2 結果分析

3.2.1 二級索引實驗

在HBase中進行查詢時通常需要利用行鍵，在不知道行鍵的情況下或通過過濾器掃描進行查找，但這樣的查詢速度非常慢。在本實驗中分別從1000萬、2000萬、3000萬和5000萬數(shù)量級的數(shù)據(jù)中查找行鍵為“34101079500229080703”，內容為“金開大道，兩路方向，10.10.79.50，1410080，2016-02-29 08:07:03，K33，02，D”的記錄，分別使用行鍵查詢和過濾器掃描兩種方法進行查找，實驗結果如圖10所示。由圖10可以看出，通過行鍵進行數(shù)據(jù)查詢的時間是毫秒級的，而利用過濾器進行掃描查詢的時間是秒級的，所以建立二級索引，在查詢前事先獲取行鍵是十分有必要的。后面將分別討論前面的三種索引獲取行鍵的性能，根據(jù)列的基數(shù)大小以及是否涉及范圍查詢選擇位圖索引、分段Hash索引和BD森林索引進行實驗，并將實驗結果與基于Solr建立的二級索引獲取行鍵的性能進行對比。

3.2.2 位圖索引實驗

在實驗數(shù)據(jù)中，車輛使用性質這一列有“非運營”“租賃”“警用”“工程搶險”等值，其基數(shù)為16;車輛類型這一列有“大型普通客車”“大型臥鋪客車”“轎車”“中型罐式貨車”等值，其基數(shù)為52。故車輛使用性質和車輛類型這兩列都屬于基數(shù)較小的列，在這兩列上進行組合條件查詢時，可以使用位圖索引。例如，要查詢車輛類型為“H37”，車輛使用性質為“K”的記錄，即查找類型為輕型自卸貨車的工程搶險車輛的過車記錄。對這兩列建立位圖索引，將屬性值為“H37”的位向量與屬性值為“K”的位向量進行按位與操作，得到這一組合條件查詢的位圖索引。對索引的位向量進行遍歷得到所需的行鍵。在1000萬、2000萬、3 000萬和5000萬數(shù)量級的數(shù)據(jù)中利用位圖索引查找類型為輕型自卸貨車的工程搶險車輛的過車記錄行鍵的時間和基于Solr獲取行鍵的時間如圖11所示。由圖11可以發(fā)現(xiàn)，位圖索引查找時間是毫秒級的且優(yōu)于基于Solr的二級索引。得到這些行鍵后，就可以在HBase中快速查到相應的記錄。

另外，位圖索引所占的存儲空間要遠小于Solr中的索引，如圖12所示，故位圖索引適用于在內存中使用。

圖10 使用行鍵查詢和過濾器掃描查詢效率比較Fig.10 Query efficiency comparison of rowkey query and filter scan

圖11 位圖索引和基于Solar索引查詢行鍵時間比較Fig.11 Time comparison of querying rowkey by bitmap index and Solar-based index

圖12 位圖索引和基于Solar索引存儲空間大小比較Fig.12 Storage space size comparison of bitmap index and Solar-based index

3.2.3 分段Hash索引實驗

當要根據(jù)車輛的電子車牌號來查詢表中的記錄時，可以在該列建立分段Hash索引來獲取相應的行鍵。在1 000萬、2000萬、3000萬和5 000萬數(shù)量級的數(shù)據(jù)中利用分段Hash索引獲取電子車牌號為“1410080”的過車記錄行鍵的時間和基于Solr獲取行鍵的時間如圖13所示，可以發(fā)現(xiàn)分段Hash索引的效果是較好的。由于使用了分段Hash索引進行了并行化的查找，故查找時間并沒有因為數(shù)據(jù)量的增加而發(fā)生陡增，基本維持在100 ms左右獲取行鍵，大大提高了查詢效率。

圖13 分段Hash索引和基于Solar索引查詢行鍵時間比較Fig.13 Time comparison of querying rowkey by segment Hash index and Solar-based index

3.2.4 BD 森林索引實驗

有時要對某輛車查詢其在一段時間內的記錄，這時涉及到時間的范圍查詢，故選擇將電子車牌號與通行時間這兩列結合在一起建立BD森林索引。在1000萬、2000萬、3000萬和5000萬數(shù)量級的數(shù)據(jù)中利用BD森林索引獲取電子車牌號為“1410080”在“2016-02-29 08:00:00”至“2016-02-29 12:00:00”期間的過車記錄行鍵的時間和基于Solr獲取行鍵的時間如圖14所示。由圖14可以看出，當數(shù)據(jù)量增大時，可以適當提高哈希表中桶的個數(shù)來維持樹的高度，但桶的個數(shù)過大也會影響范圍查詢中首尾兩哈希表的查找性能。BD森林索引由于數(shù)據(jù)結構的復雜性，故查詢時間稍長但獲取行鍵后進行查詢的綜合時間仍比通過HBase過濾器掃描的時間要短不少，獲取行鍵的時間也少于基于Solr獲取行鍵的時間。

圖14 BD森林索引和基于Solar索引查詢行鍵時間比較Fig.14 Time comparison of querying rowkey by BD forest index and Solar-based index

3.2.5 二級索引所占空間實驗

整個二級索引以RDD的形式存儲在Spark構建的內存環(huán)境中，故期望索引能夠在內存中存儲。在1 000萬、2000萬、3000萬和5000萬數(shù)量級的數(shù)據(jù)中建立整體的二級索引(包含關于車輛使用性質、車輛類型的位圖索引、關于電子車牌號的分段Hash索引以及關于電子車牌號和通行時間的BD森林索引)的空間大小如圖15所示。在當前的數(shù)據(jù)規(guī)模下索引可以在集群的2560 MB執(zhí)行內存中存儲。

圖15 二級索引空間大小Fig.15 Space size of secondary index

4 結語

本文針對HBase無法在非行鍵的列上建立索引導致條件查詢效率低下的問題建立了基于內存的二級索引。根據(jù)每列基數(shù)大小以及是否涉及范圍查詢構建不同類型的索引并進行改進，使其在Spark搭建的內存環(huán)境中進行高效的檢索。實驗結果表明這樣的二級索引大大提高了查詢效率，值得構建。對此下一步準備對索引的結構進行再次的改進，希望減小Hash索引的空間大小以及提高樹形索引的并行度，并考慮分布式索引的改進，從而繼續(xù)提高二級索引的整體性能并將其運用在實時數(shù)據(jù)處理中。