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

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

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

Bitmap索引到底是個神馬

Bitmap稱為位圖，對此不了解的童鞋可以自行Google。在此我們舉個簡單的例子來演示如何使用Bitmap Index來加速數(shù)據(jù)庫的多維查詢性能。下圖是一張典型的時序數(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列是時序列，Page、Username、Gender和City這幾個列是維度列，Added以及Removed兩列是數(shù)值列�；�于這樣的原始表，可以構(gòu)造一個典型的多維查詢?nèi)缦拢?/p>

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

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

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

原始表中，Gender列中有兩個值：Male和Female，因此需要設(shè)置兩個對應(yīng)的bitmap，Male分配一個，F(xiàn)emale分配一個，兩個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個bitmap。

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

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

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

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

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

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

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

Bitmap索引構(gòu)建時機

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

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

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

為維度列構(gòu)建維度字典是Druid中非常重要的一個步驟。維度列中的值通常都可枚舉，比如上文示例中維度列Gender只有兩個可選值：Mela和Female，City列同樣取值可枚舉。因此有必要為每個維度列構(gòu)建字典，將維度值（大多數(shù)為String）映射為Int值，大規(guī)模減少數(shù)據(jù)量。維度字典最核心的是兩個Map映射：valueToId和idToValue，以City列為例，該列有三個值，構(gòu)建出的字典就是 valueToId : <SanFrancisco, 0>, <Taiyuan,1>, <Calgary, 2>，idToValue是map反過來�？梢钥闯鰜恚瑯�(gòu)建字典就是為維度列的取值賦一個自增的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到硬盤文件的時候構(gòu)建的，那接下來就需要看看表中一行記錄過來之后如何分別為每個維度列構(gòu)建Bitmap索引。

在介紹具體的構(gòu)建流程之前，需要先說明一個關(guān)鍵的點：每個維度列實際上都會維護一個Bitmap數(shù)組：MutableBitmap[]，數(shù)組大小為每個維度列的可取值多少（Cardinality），比如Gender列只有Male和Female兩個取值，Bitmap數(shù)組大小就為2。數(shù)組的第一個值為Male對應(yīng)的位圖數(shù)據(jù)，數(shù)組的第二個值為Female對應(yīng)的位圖數(shù)據(jù)。這里就有一個問題，為什么說數(shù)組的第一個值是Male對應(yīng)的位圖數(shù)據(jù)，而不是第二個值呢？這就是用到了上文中提到的維度字典，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. 首先會為每一行生成一個自增的rowNum

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

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

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

1. Gender維度列會維護了一個位圖數(shù)組MutableBitmap[] bitmaps，里面有兩個位圖元素，下標(biāo)為0的是Male對應(yīng)的bitmap，下標(biāo)為1的是Female對應(yīng)的bitmap。初始時這兩個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ù)時，同時會為所有其他維度列構(gòu)建Bitmap索引，上述過程僅以Gender維度列作為示例，其他維度列同理可得。

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

Bitmap索引為什么需要壓縮？

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

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

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

Bitmap索引如何持久化存儲？

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

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

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

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

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

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

維度字典文件存儲

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

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

這個點是工程實踐中非常重要的一個技術(shù)點。上文中我們說數(shù)據(jù)字典在構(gòu)建的時候其實并沒有強調(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)建也是依賴于非排序的維度字典。如果此時在持久化的時候要將維度字典進(jìn)行排序，那意味著Bitmap位圖數(shù)據(jù)在Bitmap數(shù)組MutableBitmap[]中的位置也需要相應(yīng)的變化，保持一致。

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

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

Bitmap索引文件存儲

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

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

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

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

這樣一個過程實際上可以分為兩步：

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

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

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

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

因為文件中維度值是由小到大排序的，所以查找的戰(zhàn)術(shù)思想是二分查找。首先將查找指針移動到header文件的中心，中心下標(biāo)curIndex = (minIndex,maxIndex)>>>1，header文件的中心值為offset_SanFrancisco，這個offset實際上指向了value文件中的San Francisco（這里忽略了一些細(xì)節(jié)），這個值與我們要找的值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ù)，兩者使用與運算就可以得到一個最終的Bitmap位圖索引，這個位圖索引我們稱為Cursor。

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

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

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

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

其他需要考慮的問題

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

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

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

Inverted Index（倒排索引）工程實踐

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

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

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

2. Bitmap使用intersection實現(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ù)據(jù)庫中，InfluxDB和HiTSDB都使用了倒排索引來加速多維度查詢，倒排索引會首先在內(nèi)存中構(gòu)建并持久化到文件（或HBase），在使用時再將索引加載到內(nèi)存。

文章總結(jié)

這是很早之前花時間將之前研究的Bitmap索引知識整理了出來，拿出來和大家分享。本文從理論和工程實踐兩個方面對Bitmap索引的工作原理進(jìn)行了深入的介紹，筆者認(rèn)為文章的核心在于如何在工程實踐中將Bitmap索引這么一個大命題分解成五個子命題，每個子命題中我們又應(yīng)該重點關(guān)注哪些技術(shù)點。不得不說，要講清楚Bitmap索引的工程實踐確實有一定難度，文中或多或少會有一些難于理解的地方甚至紕漏。還忘各位看官擔(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)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。