時(shí)序數(shù)據(jù)庫從抽象語義上來說總體可以概括為兩個(gè)方面的基本需求，一個(gè)方面是存儲層面的基本需求：包括LSM寫入模型保證寫入性能、數(shù)據(jù)分級存儲（最近2小時(shí)的數(shù)據(jù)存儲在內(nèi)存中，最近一天的數(shù)據(jù)存儲在SSD中，一天以后的數(shù)據(jù)存儲在HDD中）保證查詢性能以及存儲成本、數(shù)據(jù)按時(shí)間分區(qū)保證時(shí)間線查詢性能。另一方面是查詢層面的基本需求：包括基本的按時(shí)間線進(jìn)行多個(gè)維度的原始數(shù)據(jù)查詢、按時(shí)間線在多個(gè)維度進(jìn)行聚合后的數(shù)據(jù)統(tǒng)計(jì)查詢需求以及TopN需求等。

可見，多維條件查詢通常是時(shí)序數(shù)據(jù)庫的一個(gè)硬需求，其性能好壞也是評價(jià)一個(gè)時(shí)序數(shù)據(jù)庫是否優(yōu)秀的一個(gè)重要指標(biāo)。調(diào)研了市場上大多時(shí)序數(shù)據(jù)庫（InfluxDB、Druid、OpenTSDB、HiTSDB等），基本上都支持多維查詢，只有極個(gè)別的暫時(shí)支持的并不完美。通常來說，支持多維查詢的手段無非兩種：Bitmap Index以及Inverted Index，也稱為位圖索引和倒排索引。

接下來筆者會重點(diǎn)介紹使用Bitmap索引來加快多維條件查詢的基本原理以及工程實(shí)踐，最后也會對倒排索引進(jìn)行一個(gè)簡單的介紹。其實(shí)這兩種索引無論在原理上還是在工程實(shí)踐上都極其相似，只是在幾個(gè)小的細(xì)節(jié)問題上有所不同，在文章最后筆者也會進(jìn)行詳細(xì)的說明。

Bitmap索引到底是個(gè)神馬

Bitmap稱為位圖，對此不了解的童鞋可以自行Google。在此我們舉個(gè)簡單的例子來演示如何使用Bitmap Index來加速數(shù)據(jù)庫的多維查詢性能。下圖是一張典型的時(shí)序數(shù)據(jù)表：

Timestamp	Page	Username	Gender	City	Added	Removed
2011-01-01T01:00:00Z	Justin Bieber	Boxer	Male	San Francisco	1800	25
2011-01-01T01:00:00Z	Justin Bieber	Reach	Female	Taiyuan	2912	42
2011-01-01T02:00:00Z	Ke$ha	Helz	Female	Calgary	1953	17
2011-01-01T02:00:00Z	Ke$ha	Xeno	Male	Taiyuan	3194	170

圖中Timestamp列是時(shí)序列，Page、Username、Gender和City這幾個(gè)列是維度列，Added以及Removed兩列是數(shù)值列�；�于這樣的原始表，可以構(gòu)造一個(gè)典型的多維查詢?nèi)缦拢?/p>

select Added from datasource where Gender = ‘Female’ and City = ‘Taiyuan’

查詢中使用兩個(gè)維度條件進(jìn)行過濾，分別是Gender以及City列。很顯然，如果不使用任何技術(shù)手段的話，在原始表上根據(jù)如上兩個(gè)維度的過濾條件進(jìn)行查詢需要遍歷整個(gè)原始表，并對相應(yīng)維度列進(jìn)行過濾，這個(gè)代價(jià)很顯然是非常可觀的。那能不能有一種方法可以直接根據(jù)維度的過濾條件得到待查找目標(biāo)行，比如上述示例中能不能根據(jù)Gender = ‘Female’ and City = ‘Taiyuan’這兩個(gè)過濾條件直接定位到待查找目標(biāo)行就是第二行，其他行都不滿足條件，這樣的話只需要查找第二行的Added列返回給用戶即可，不再需要野蠻的全表掃描并一條一條數(shù)據(jù)進(jìn)行對比。這就是Bitmap索引（倒排索引）的使命！

使用Bitmap索引的基本原理是將這兩列上的數(shù)值映射到bitmap上，再采用intersection表示來實(shí)現(xiàn)and、or等這種查詢謂詞。在上述示例中，將Gender以及City兩列映射成bitmap如下圖所示：

原始表中，Gender列中有兩個(gè)值：Male和Female，因此需要設(shè)置兩個(gè)對應(yīng)的bitmap，Male分配一個(gè)，F(xiàn)emale分配一個(gè)，兩個(gè)bitmap的大小對應(yīng)原始表的數(shù)據(jù)行數(shù)，原始數(shù)據(jù)有4行，bitmap的大小就是4。再看原始表的Gender列，行1和行4是Male，行2和行3是Female。因此將Male對應(yīng)的bitmap中坐標(biāo)為1和4的值置為1，其他兩位置為0。Female對應(yīng)的bitmap中坐標(biāo)為2和3的值置為1，其他兩位置為0。

這樣的bitmap表示什么意思呢？以Male對應(yīng)的bitmap來說，下標(biāo)是1和4的值為1就表示原始表中這一列的第一行和第4行的值為Male。同理，F(xiàn)emale對應(yīng)的bitmap中下標(biāo)是2和3對應(yīng)的值為1表示原始表中這一列的第2行和第3行的值為Female。同樣的道理，City列可以表示為上圖右側(cè)3個(gè)bitmap。

可見，每個(gè)維度列有多少種取值（Cardinality），這個(gè)維度列就會有多少個(gè)Bitmap。每個(gè)Bitmap表示對應(yīng)取值在原始表中哪些行出現(xiàn)過。

這樣表示完成之后，再來看看查詢語句：where Gender = ‘Female’ and City = ‘Taiyuan’，就可以使用對應(yīng)bitmap表示為如下形式：

分別拿出 Gender = ‘Female’ and City = ‘Taiyuan’ 對應(yīng)的bitmap，執(zhí)行and操作實(shí)際上對應(yīng)位圖的與運(yùn)算，最終得到一個(gè)結(jié)果位圖，結(jié)果位圖中只有下標(biāo)2的值置為1，說明原始表中滿足查詢條件的行只有第二行。接下來的工作就是怎么查詢第二行的Added數(shù)值，這里就不再贅述。

很多講解位圖索引的博客對位圖索引的介紹大多到此為止，僅僅介紹位圖索引的工作原理。本文在介紹位圖索引工作原理的基礎(chǔ)上還會進(jìn)一步深入介紹在真實(shí)的工程實(shí)踐中整個(gè)位圖索引工作體系。本文以Druid系統(tǒng)的目標(biāo)，對Druid中位圖索引的工作原理深入分析。主要包括如下幾個(gè)部分：

之前在一個(gè)開源項(xiàng)目中實(shí)現(xiàn)過一個(gè)倒排索引功能，其實(shí)與Bitmap索引實(shí)現(xiàn)原理基本一致。因?yàn)樵谥�前并沒有接觸過倒排索引相關(guān)的實(shí)踐知識，因此頭腦中也沒有非常完整的勾勒出這個(gè)功能的核心體系，在實(shí)現(xiàn)的時(shí)候才發(fā)現(xiàn)這樣那樣的問題，雖說最后也實(shí)現(xiàn)了功能，現(xiàn)在想來整個(gè)系統(tǒng)的模塊化設(shè)計(jì)并不是非常考究。經(jīng)過倒排索引項(xiàng)目的洗禮，再結(jié)合這段時(shí)間對Druid中Bitmap索引實(shí)現(xiàn)的研究，才將Bitmap索引這樣一個(gè)大功能分解成上圖中的五個(gè)小功能，每個(gè)小功能都是一個(gè)獨(dú)立模塊，筆者認(rèn)為任何對Bitmap索引的工程實(shí)現(xiàn)都可以參考這五個(gè)模塊進(jìn)行設(shè)計(jì)思考。接下來就以Druid中Bitmap索引的實(shí)現(xiàn)分別就這五個(gè)小功能的細(xì)節(jié)問題進(jìn)行深入分析。

Bitmap索引如何在內(nèi)存中構(gòu)建？

Druid數(shù)據(jù)實(shí)時(shí)寫入節(jié)點(diǎn)采用LSM結(jié)構(gòu)保證數(shù)據(jù)的寫入性能。數(shù)據(jù)先寫入內(nèi)存，每隔10min（可配）會將內(nèi)存中的數(shù)據(jù)persist到本地硬盤形成文件，然后會有一個(gè)線程再每隔1h（可配）將本地硬盤的多個(gè)文件合并成一個(gè)segment。

Bitmap索引構(gòu)建時(shí)機(jī)

這里實(shí)際上會碰到第一個(gè)需要權(quán)衡的問題：Bitmap索引是應(yīng)該在數(shù)據(jù)寫入的同時(shí)實(shí)時(shí)構(gòu)建呢，還是應(yīng)該在數(shù)據(jù)從內(nèi)存persist到硬盤的時(shí)候批量構(gòu)建。很顯然，實(shí)時(shí)構(gòu)建會對數(shù)據(jù)寫入吞吐量造成一定影響，實(shí)際測試下來發(fā)現(xiàn)寫入性能會下降5%到15%，而且表維度越多，性能下降越明顯。而另一方面，如果是批量構(gòu)建，那么內(nèi)存中的數(shù)據(jù)實(shí)際上是沒有索引的，這部分?jǐn)?shù)據(jù)的檢索方式必然與已經(jīng)持久化到硬盤文件數(shù)據(jù)的檢索方式完全不同：內(nèi)存中的數(shù)據(jù)檢索不走索引直接查數(shù)據(jù)，文件中的數(shù)據(jù)檢索需要先走索引再查數(shù)據(jù)，在實(shí)際查詢實(shí)現(xiàn)中需要分別處理。

Druid中Bitmap的構(gòu)建時(shí)機(jī)采用的后者，即在數(shù)據(jù)從內(nèi)存persist到硬盤的時(shí)候批量構(gòu)建。本人實(shí)現(xiàn)倒排索引時(shí)采用的是前者，主要考慮的問題是希望無論數(shù)據(jù)是在內(nèi)存還是在硬盤，都能夠采用統(tǒng)一的檢索方式，即都先根據(jù)索引查詢行號，再根據(jù)行號查具體數(shù)據(jù)。這樣將內(nèi)存檢索和硬盤檢索統(tǒng)一處理的好處是在代碼實(shí)現(xiàn)上更加方便，更加簡潔。當(dāng)然，會犧牲一部分寫入性能。

維度列構(gòu)建維度字典

為維度列構(gòu)建維度字典是Druid中非常重要的一個(gè)步驟。維度列中的值通常都可枚舉，比如上文示例中維度列Gender只有兩個(gè)可選值：Mela和Female，City列同樣取值可枚舉。因此有必要為每個(gè)維度列構(gòu)建字典，將維度值（大多數(shù)為String）映射為Int值，大規(guī)模減少數(shù)據(jù)量。維度字典最核心的是兩個(gè)Map映射：valueToId和idToValue，以City列為例，該列有三個(gè)值，構(gòu)建出的字典就是 valueToId : <SanFrancisco, 0>, <Taiyuan,1>, <Calgary, 2>，idToValue是map反過來。可以看出來，構(gòu)建字典就是為維度列的取值賦一個(gè)自增的Int值。

同理，可以分別為Page列、UserName列和Gender列構(gòu)建相應(yīng)的維度字典，構(gòu)建完成之后，原始表中第三行的所有維度列就不再是Page:Ke$ha, UserName:Helz, Gender:Female, City:Calgary，而是[1, 2, 1, 2]。

構(gòu)建Bitmap索引

上文說到Druid中Bitmap索引是在內(nèi)存數(shù)據(jù)異步persist到硬盤文件的時(shí)候構(gòu)建的，那接下來就需要看看表中一行記錄過來之后如何分別為每個(gè)維度列構(gòu)建Bitmap索引。

在介紹具體的構(gòu)建流程之前，需要先說明一個(gè)關(guān)鍵的點(diǎn)：每個(gè)維度列實(shí)際上都會維護(hù)一個(gè)Bitmap數(shù)組：MutableBitmap[]，數(shù)組大小為每個(gè)維度列的可取值多少（Cardinality），比如Gender列只有Male和Female兩個(gè)取值，Bitmap數(shù)組大小就為2。數(shù)組的第一個(gè)值為Male對應(yīng)的位圖數(shù)據(jù)，數(shù)組的第二個(gè)值為Female對應(yīng)的位圖數(shù)據(jù)。這里就有一個(gè)問題，為什么說數(shù)組的第一個(gè)值是Male對應(yīng)的位圖數(shù)據(jù)，而不是第二個(gè)值呢？這就是用到了上文中提到的維度字典，Male對應(yīng)的維度字典值為0，就對應(yīng)數(shù)組下標(biāo)為0；Female對應(yīng)的維度字典值為1，對應(yīng)數(shù)據(jù)下標(biāo)就為1。

下面以其中一行數(shù)據(jù)為例介紹構(gòu)建Bitmap索引的過程：

1. 首先會為每一行生成一個(gè)自增的rowNum

2. 遍歷所有維度列，分別為每個(gè)維度列構(gòu)建相應(yīng)的Bitmap數(shù)組

• 針對某個(gè)緯度列的value值，首先在維度字典中根據(jù)value找到對應(yīng)的id，這個(gè)id即是Bitmap數(shù)組的下標(biāo)，根據(jù)這個(gè)下標(biāo)找到該value對應(yīng)的位圖數(shù)據(jù)，即MutableBitmap[id]
• 定位到位圖數(shù)據(jù)之后，再將該位圖下標(biāo)為rowNum的bit位置為1

為了更加具體地理解整個(gè)Bitmap索引構(gòu)建的過程，我們以上文中Gender維度列為例模擬構(gòu)建的過程：

1. Gender維度列會維護(hù)了一個(gè)位圖數(shù)組MutableBitmap[] bitmaps，里面有兩個(gè)位圖元素，下標(biāo)為0的是Male對應(yīng)的bitmap，下標(biāo)為1的是Female對應(yīng)的bitmap。初始時(shí)這兩個(gè)bitmap中都沒有任何數(shù)字。

2. 遍歷第一行（rowNum = 0），值為Male，根據(jù)維度字典找到對應(yīng)的id位0，即Male對應(yīng)的位圖數(shù)據(jù)為bitmaps[0]，將bitmaps[0]下標(biāo)0（rowNum為0）的bit位置為1，得到：

3. 遍歷第二行（rowNum = 1），值為Female，根據(jù)維度字典找到對應(yīng)的id位1，即Male對應(yīng)的位圖數(shù)據(jù)為bitmaps[1]，將bitmaps[1]下標(biāo)1（rowNum為1）的bit位置為1，得到：

4. 遍歷第三行（rowNum = 2），值為Female，根據(jù)維度字典找到對應(yīng)的id位1，即Male對應(yīng)的位圖數(shù)據(jù)為bitmaps[1]，將bitmaps[1]下標(biāo)2（rowNum為2）的bit位置為1，得到：

5. 遍歷第一行（rowNum = 3），值為Male，根據(jù)維度字典找到對應(yīng)的id位0，即Male對應(yīng)的位圖數(shù)據(jù)為bitmaps[0]，將bitmaps[0]下標(biāo)3（rowNum為3）的bit位置為1，得到：

這樣，就可以得到Gender維度列的Bitmap索引。當(dāng)然，遍歷一行數(shù)據(jù)時(shí)，同時(shí)會為所有其他維度列構(gòu)建Bitmap索引，上述過程僅以Gender維度列作為示例，其他維度列同理可得。

Bitmap索引如何進(jìn)行壓縮處理？

Bitmap索引為什么需要壓縮？

還是以Gender列為例，上文我們知道這個(gè)維度列只有兩個(gè)取值：Male和Female，因此無論對于Male對應(yīng)的位圖數(shù)據(jù)，還是Female對應(yīng)的位圖數(shù)據(jù)，都會存在大量的連續(xù)的0或者連續(xù)的1，非常適合壓縮編碼，減小存儲空間。

Bitmap索引如何進(jìn)行壓縮？

針對Bitmap的壓縮有非常多的算法，大家可以自行Google。根據(jù)壓縮效率、解碼效率以及intersection等計(jì)算效率等指標(biāo)的權(quán)衡，特別推薦使用RoaringBitmap壓縮算法。有興趣的同學(xué)可以自行Google。

Bitmap索引如何持久化存儲？

Druid中原始數(shù)據(jù)每隔一段時(shí)間就會落盤一次，隨著原始數(shù)據(jù)的落盤，原始數(shù)據(jù)中維度列對應(yīng)的Bitmap索引也需要執(zhí)行持久化存儲。在實(shí)際實(shí)現(xiàn)中，Druid首先將維度字典持久化到文件，再將原始數(shù)據(jù)（維度列都使用維度字典編碼處理）持久化到文件，最后再將維度列對應(yīng)的Bitmap索引持久化到文件。

對于Druid系統(tǒng)來說，這里需要關(guān)注兩點(diǎn)：

1. Druid系統(tǒng)是列式存儲系統(tǒng)，同一個(gè)segment中所有列的數(shù)據(jù)都會分別獨(dú)立存儲在一起形成多個(gè)列文件，比如City列的數(shù)據(jù)會存儲在一起形成文件，Added列的數(shù)據(jù)會存儲在一起形成文件。其他列同理。

2. Druid系統(tǒng)中的文件分為兩種，一種是定長文件格式，一種是非定長文件格式。定長文件針對于列數(shù)值是定長的，比如某些數(shù)值列是Double的，有些數(shù)據(jù)列是Long類型，再比如維度列經(jīng)過編碼之后所有維度列都是Int類型，時(shí)間列是Long類型。這些定長文件格式很簡單，直接存儲數(shù)值即可。而非定長文件通常主要針對列數(shù)值不是定長的，比如維度字典文件中需要存儲維度值，這些維度值通常是字符串，并不定長；比如Bitmap索引的存儲文件中需要存儲Bitmap位圖數(shù)據(jù)，這些值也不是定長的。下文主要介紹Bitmap索引的存儲，所以重點(diǎn)介紹非定長文件格式。

Druid中非定長數(shù)值存儲的文件格式如下圖所示：

可以看出，Druid系統(tǒng)中使用了3個(gè)文件來存儲非定長數(shù)據(jù)：meta文件，header文件以及value文件，其中meta文件主要存儲一些元數(shù)據(jù)信息，比如存儲數(shù)值個(gè)數(shù)、存儲數(shù)值總大小等；value文件存儲實(shí)際的數(shù)值，一個(gè)數(shù)值一個(gè)數(shù)值寫進(jìn)去，在實(shí)際數(shù)據(jù)之前有一個(gè)int值表示該數(shù)值的大�。籬eader文件實(shí)際上是value文件中每個(gè)數(shù)值在value文件的偏移量，文件中每個(gè)值都是一個(gè)int。

維度字典文件存儲

緯度列數(shù)據(jù)字典在數(shù)據(jù)寫入的時(shí)候就會構(gòu)建，并一直保存在內(nèi)存。Druid會在persist的時(shí)候?qū)⑵涑志没�形成維度字典文件，每個(gè)維度列的字典會單獨(dú)形成一個(gè)文件，比如Gender維度列的數(shù)據(jù)字典會形成一個(gè)文件，City維度列的數(shù)據(jù)字典會形成另一個(gè)文件。下圖是City維度列形成的維度列字典文件格式（沒有列出meta文件）：

City維度列的數(shù)據(jù)字典一共有3個(gè)值：Calgary、San Francisco和Taiyuan，持久化到文件后就是上圖格式，需要特別注意的是：數(shù)據(jù)字典的值是按照字典序由小到大排列之后存入文件的。比如上圖中Calgary、San Francisco和Taiyuan就是按照由小到大排序后存儲的。

這個(gè)點(diǎn)是工程實(shí)踐中非常重要的一個(gè)技術(shù)點(diǎn)。上文中我們說數(shù)據(jù)字典在構(gòu)建的時(shí)候其實(shí)并沒有強(qiáng)調(diào)排序，而是按照維度列進(jìn)來系統(tǒng)的順序構(gòu)建字典的，比如San Francisco先進(jìn)入系統(tǒng)，在第一行，所以San Francisco對應(yīng)的編碼值就為0，Taiyuan是第二行，所以Taiyuan對應(yīng)的編碼值為1，同理，Calgary編碼值為2。而且，Bitmap索引構(gòu)建也是依賴于非排序的維度字典。如果此時(shí)在持久化的時(shí)候要將維度字典進(jìn)行排序，那意味著Bitmap位圖數(shù)據(jù)在Bitmap數(shù)組MutableBitmap[]中的位置也需要相應(yīng)的變化，保持一致。

為什么需要排序？如果不排序直接存儲行不行？

解答這個(gè)問題之前先看看維度字典文件，可以得到文件中只存儲了維度列的值，并沒有存儲對應(yīng)的編碼值，那編碼值哪去了？實(shí)際上編碼值隱含在維度列值的下標(biāo)，比如Calgary是第一個(gè)值，那對應(yīng)的編碼值就是0，Taiyuan是第三個(gè)值，對應(yīng)的編碼值就是2�；�于這樣的事實(shí)，如果不排序，你來告訴我如果說我想查Taiyuan對應(yīng)的編碼值，如何查？那就蒙圈了，需要一個(gè)一個(gè)遍歷的查，如果某個(gè)維度Cardinality很大的話，不就跪了。而反過來，如果排序的話，就可以通過二分查找來查，下文會舉例介紹。

Bitmap索引文件存儲

Bitmap索引文件和維度字典文件是一一對應(yīng)的，每個(gè)維度列的Bitmap索引會單獨(dú)形成一個(gè)文件，比如Gender維度列的Bitmap索引會形成一個(gè)文件，City維度列的Bitmap索引會形成一個(gè)文件。下圖是City維度列形成的Bitmap索引文件：

注意，Bitmap索引文件中Bitmap位圖數(shù)據(jù)的存儲順序必須和維度字典中對應(yīng)值的存儲順序一致。比如維度字典中Calgary存儲在文件中第一的位置，對應(yīng)的Bitmap位圖就必須存儲在相應(yīng)第一的位置。

查詢時(shí)如何根據(jù)Bitmap索引構(gòu)建Cursor體系？

以查詢語句select Added from datasource where Gender = ‘Female’ and City = ‘Taiyuan’為例，看看如何實(shí)現(xiàn)將where Gender = ‘Female’ and City = ’Taiyuan’這么一個(gè)多維度過濾條件轉(zhuǎn)化成如下Bitmap與運(yùn)算的結(jié)果：

這樣一個(gè)過程實(shí)際上可以分為兩步：

1. 如何根據(jù)Gender = ‘Female’找到對應(yīng)的位圖數(shù)據(jù)？同理，如何根據(jù)City = ’Taiyuan’找到對應(yīng)的位圖數(shù)據(jù)？

2. 如何根據(jù)and操作符實(shí)現(xiàn)位圖與操作？

根據(jù)and操作符實(shí)現(xiàn)位圖與操作是比較簡單的，現(xiàn)在很多Bitmap實(shí)現(xiàn)包中都有類似的功能，在此不再贅述。因此構(gòu)建Cursor體系實(shí)際上就簡化為根據(jù)維度過濾條件查找對應(yīng)的位圖數(shù)據(jù)這樣一個(gè)問題。為了更加具體，我們以City = ’Taiyuan’為例定位對應(yīng)的位圖數(shù)據(jù)。整個(gè)過程分為如下幾個(gè)部分：

1. 在City列對應(yīng)的維度字典文件中查找’Taiyuan’值在文件中的下標(biāo)

因?yàn)槲募�中維度值是由小到大排序的，所以查找的戰(zhàn)術(shù)思想是二分查找。首先將查找指針移動到header文件的中心，中心下標(biāo)curIndex = (minIndex,maxIndex)>>>1，header文件的中心值為offset_SanFrancisco，這個(gè)offset實(shí)際上指向了value文件中的San Francisco（這里忽略了一些細(xì)節(jié)），這個(gè)值與我們要找的值Taiyuan相比較，很顯然前者小于后者，因此繼續(xù)往后找。經(jīng)過多次的查找，最終定位到Taiyuan對應(yīng)的下標(biāo)是2（從0開始哦）。

2. 在City列對應(yīng)的Bitmap索引文件中查找下標(biāo)為2的Bitmap位圖數(shù)據(jù)，如下圖所示，首先在header文件中找到下標(biāo)為2的offset為offset_ty_bm，再根據(jù)偏移值在value文件中定位出Taiyuan對應(yīng)的bitmap位圖數(shù)據(jù)。（忽略具體的查找細(xì)節(jié)）

經(jīng)過這兩步的執(zhí)行就可以根據(jù)City = ’Taiyuan’得到對應(yīng)的bitmap位圖數(shù)據(jù)，同理，根據(jù)Gender = ‘Female’可以得到對應(yīng)的bitmap位圖數(shù)據(jù)，兩者使用與運(yùn)算就可以得到一個(gè)最終的Bitmap位圖索引，這個(gè)位圖索引我們稱為Cursor。

如何根據(jù)Cursor體系快速查找對應(yīng)行數(shù)據(jù)？

Cursor結(jié)構(gòu)體構(gòu)建出來之后，如果根據(jù)這個(gè)結(jié)構(gòu)快速的查找對應(yīng)的行數(shù)據(jù)呢？這個(gè)過程也可以分為兩步：

1. 根據(jù)上文介紹知道Cursor結(jié)構(gòu)體實(shí)際上就是一個(gè)bitmap，bitmap中置為1的下標(biāo)表示該行數(shù)據(jù)符合過濾條件。因此需要順序遍歷這個(gè)bitmap的所有位，如果目標(biāo)位為1，表示該目標(biāo)位下標(biāo)對應(yīng)的行滿足過濾條件，需要將該行的對應(yīng)數(shù)據(jù)找出來返回給用戶。否則不滿足過濾條件，直接跳過。

2. 假如bitmap中下標(biāo)為的位置值為1，表示第二行滿足過濾條件，因此需要查找第二行Added列的值。實(shí)現(xiàn)起來很簡單，因?yàn)樵摿械乃�有值都存儲在一個(gè)文件中，而且每個(gè)值都定長（都是Int），因此可以很快的在文件中加載出startOffset為Ints.Bytes，endOffset為2*Ints.Bytes的值，即為Added的值。

其他需要考慮的問題

講到這里，筆者基本上已經(jīng)將Bitmap索引的工程實(shí)踐需要考量的技術(shù)點(diǎn)都做了介紹，但還有幾個(gè)點(diǎn)需要考慮：

1. Bitmap索引目前僅支持寫入，不支持更新。如果需要支持更新，需要做另外的考慮。

2. Bitmap索引文件需要在segment合并的時(shí)候也執(zhí)行合并，合并的過程實(shí)際上也是一行一行的讀出來，然后再根據(jù)上述過程生成一個(gè)新的Bitmap索引文件。

Inverted Index（倒排索引）工程實(shí)踐

筆者之前在一個(gè)開源項(xiàng)目中實(shí)現(xiàn)了倒排索引功能，現(xiàn)在看來，基本實(shí)現(xiàn)思路和上述過程基本一致，核心不同點(diǎn)在于：倒排索引中每個(gè)維度列取值不再對應(yīng)bitmap，而是對應(yīng)一個(gè)列表。舉個(gè)栗子，Bitmap索引體系中，Gender維度列中Male對應(yīng)一個(gè)bitmap是[1,0,0,1]。換成倒排索引，Gender維度列中Male對應(yīng)的不再是bitmap，而是一個(gè)List : [0,2]，分別表示第1行和第三行。

除此之外，還有一些實(shí)現(xiàn)細(xì)節(jié)有些許不同：

1. Bitmap壓縮性能通常沒有倒排索引中List壓縮效果好，前者會存在較大的存儲空間開銷。

2. Bitmap使用intersection實(shí)現(xiàn)and、or等操作的性能要好于倒排索引的List結(jié)構(gòu)，后者需要從小到大遍歷查找

3. 使用Bitmap構(gòu)建的Cursor加速原始數(shù)據(jù)查找，需要遍歷bitmap來找哪一行滿足條件，只有bit位是1的才滿足條件；而倒排索引構(gòu)建的Cursor不需要查找，List中的數(shù)值就直接對應(yīng)行號。

在常見的時(shí)序數(shù)據(jù)庫中，InfluxDB和HiTSDB都使用了倒排索引來加速多維度查詢，倒排索引會首先在內(nèi)存中構(gòu)建并持久化到文件（或HBase），在使用時(shí)再將索引加載到內(nèi)存。

文章總結(jié)

這是很早之前花時(shí)間將之前研究的Bitmap索引知識整理了出來，拿出來和大家分享。本文從理論和工程實(shí)踐兩個(gè)方面對Bitmap索引的工作原理進(jìn)行了深入的介紹，筆者認(rèn)為文章的核心在于如何在工程實(shí)踐中將Bitmap索引這么一個(gè)大命題分解成五個(gè)子命題，每個(gè)子命題中我們又應(yīng)該重點(diǎn)關(guān)注哪些技術(shù)點(diǎn)。不得不說，要講清楚Bitmap索引的工程實(shí)踐確實(shí)有一定難度，文中或多或少會有一些難于理解的地方甚至紕漏。還忘各位看官擔(dān)待指正！

 

來自：http://hbasefly.com/2018/06/19/timeseries-database-8/

 

標(biāo)簽： Google ssd 代碼 數(shù)據(jù)庫

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。