為什么 ElasticSearch 比 MySQL 更適合復(fù)雜條件搜索
熟悉 MySQL 的同學(xué)一定都知道，MySQL 對(duì)于復(fù)雜條件查詢的支持并不好。MySQL 最多使用一個(gè)條件涉及的索引來(lái)過(guò)濾，然后剩余的條件只能在遍歷行過(guò)程中進(jìn)行內(nèi)存過(guò)濾 。
上述這種處理復(fù)雜條件查詢的方式因?yàn)橹荒芡ㄟ^(guò)一個(gè)索引進(jìn)行過(guò)濾，所以需要進(jìn)行大量的 I/O 操作來(lái)讀取行數(shù)據(jù)，并消耗 CPU 進(jìn)行內(nèi)存過(guò)濾，導(dǎo)致查詢性能的下降。
而 ElasticSearch 因其特性，十分適合進(jìn)行復(fù)雜條件查詢，是業(yè)界主流的復(fù)雜條件查詢場(chǎng)景解決方案，廣泛應(yīng)用于訂單和日志查詢等場(chǎng)景。
下面我們就一起來(lái)看一下，為什么 ElasticSearch 適合進(jìn)行復(fù)雜條件查詢。
ElasticSearch 簡(jiǎn)介
Elasticsearch 是開(kāi)源的實(shí)時(shí)分布式搜索分析引擎，內(nèi)部使用 Lucene 做索引與搜索。它提供"準(zhǔn)實(shí)時(shí)搜索"能力，并且能動(dòng)態(tài)集群規(guī)模，彈性擴(kuò)容。
Elasticsearch 使用 Lucene 作為其全文搜索引擎，用于處理純文本的數(shù)據(jù)，但 Lucene 只是一個(gè)庫(kù)，提供建立索引、執(zhí)行搜索等接口，但不包含分布式服務(wù)，這些正是 Elasticsearch 做的。
下面，我們來(lái)介紹一下 ElasticSearch 的相關(guān)概念。為了便于初學(xué)者理解，我們先將 ElasticSearch 中的概念和 MySQL 中的概念大致地進(jìn)行對(duì)應(yīng)。但是二者在具體細(xì)節(jié)上還是有很多差異的，大家深入了解 ElasticSearch 就會(huì)將二者區(qū)分清楚，不能強(qiáng)行對(duì)比等同。
ElasticSearch 中的索引 Index 類似于 MySQL 中的數(shù)據(jù)庫(kù) Database；
ElasticSearch 中的類型 Type 類似于 MySQL 中的表 Table；需要注意，這個(gè)概念在 7.x 版本中被完全刪除，而且概念上和 Table 也有較大差異；
ElasticSearch 中的文檔 Document 類似于 MySQL 中的數(shù)據(jù)行 Row，每個(gè)文檔由多個(gè)字段 Filed 組成，這個(gè)Filed 就類似于 MySQL 的 Column；
ElasticSearch 中的映射 Mapping 是對(duì)索引庫(kù)中的索引字段及其數(shù)據(jù)類型進(jìn)行定義，類似于關(guān)系型數(shù)據(jù)庫(kù)中的表結(jié)構(gòu) Schema；
ElasticSearch 使用自己的領(lǐng)域語(yǔ)言 Query DSL 來(lái)進(jìn)行增刪改查，而 MySQL 使用 SQL 語(yǔ)言進(jìn)行上訴操作。
ElasticSearch 還有一系列有關(guān)其分布式特性的概念，我們這里就暫不介紹了，等后續(xù)學(xué)習(xí)到其分布式特性時(shí)在進(jìn)行介紹。
倒排索引
MySQL 有 B+ 樹(shù)索引，而 ElasticSearch 則是倒排索引 (Inverted Index)，它通過(guò)倒排索引來(lái)實(shí)現(xiàn)比 MySQL 更快的過(guò)濾和復(fù)雜條件的查詢，此外，全文搜索功能也是依賴倒排索引才能實(shí)現(xiàn)。下面，我們就具體來(lái)看一下何為倒排索引。
倒排索引按照維基百科的描述，是存儲(chǔ)文檔內(nèi)容到文檔位置映射關(guān)系的數(shù)據(jù)庫(kù)索引結(jié)構(gòu)。不過(guò)只看定義，我是有點(diǎn)迷惑，這不是和 MySQL 的非主鍵索引類似嘛，為什么要叫它“倒排”呢？這個(gè)問(wèn)題我目前也為搞清楚，可能要等到后續(xù)了解了其具體實(shí)現(xiàn)才能理解。
我們還是以書籍檢索為例，假設(shè)有以下數(shù)據(jù)，每一行就是一個(gè) Document，每個(gè) Document 由 id，ISBN 號(hào)，作者名稱和評(píng)分組成。
給上述數(shù)據(jù)按照 ISBN 和 Author 建立的倒排索引如下所示。倒排索引是每個(gè)字段分開(kāi)建立的，相互獨(dú)立。有兩個(gè)專門的術(shù)語(yǔ)，分別是索引 Term 和倒排表 Posting List。字段的值就是 Term，比如 N0007，而 Term 對(duì)應(yīng)的文檔 ID 的列表就是 Posting List，對(duì)應(yīng)圖中紅色的部分。
一般 Term 都是按照順序排序的，比如 Author 名稱就是按照字母序進(jìn)行了排序，排序之后，當(dāng)我們搜索某一個(gè) Term 時(shí)，就不需要從頭遍歷，而是采用二分查找。一系列排序后的 Term 就組成了索引表 Term Dictionary。
但是 Term Dictionary 往往很大，無(wú)法完整放入內(nèi)存，這是為了更快的查詢，還需要再給它創(chuàng)建索引，也就是 Term Index 。
ElasticSearch 使用 Burst-Trie 結(jié)構(gòu)來(lái)實(shí)現(xiàn) Term Index，它是一種前綴樹(shù) Trie 的一種變種，它主要是將后綴進(jìn)行了壓縮，降低了Trie的高度，從而獲取更好查詢性能。
Term Index 并不需要像 MySQL 的索引一樣，包含所有的 Term，而是包含的是這些 Term 的前綴。它就類似于字典的查詢目錄，可以進(jìn)行快速定位到 Term Dictionary 的某一位置，然后再?gòu)倪@個(gè)位置向后查詢。
綜上， Alice，Alf，Arlan，Bob，Tom 等詞的倒排索引如下所示。綠色部分是 Term Index，藍(lán)色部分是 Term Dictionary，紅色部分是 Posting List。
一般來(lái)說(shuō)，Term Index 都是全部緩存在內(nèi)存中，查詢時(shí)，先通過(guò)其快速定位到 Term Dictionary 對(duì)應(yīng)的大致范圍，然后再進(jìn)行磁盤讀取查找對(duì)應(yīng)的 Term，這樣就大大減少了磁盤 I/O 的次數(shù)。
聯(lián)合索引查詢
了解了 ElasticSearch 的倒排索引后，我們?cè)賮?lái)看看其如何處理復(fù)雜的聯(lián)合索引查詢。比如上述書籍例子中，我們需要查詢?cè)u(píng)分等于2.2并且作者名稱叫 Tom的書籍。
理論上，我們只需要分別按照 Score 和 Author 字段的倒排索引進(jìn)行查詢，獲取響應(yīng)的 Posting List，再將其做交集合并即可。
這里又要吐槽一下 MySQL，它是不支持這個(gè)合并操作的，它只能按照一個(gè)字段的索引進(jìn)行查詢，然后根據(jù)另外一個(gè)字段的條件做內(nèi)存過(guò)濾。順便說(shuō)一下，MySQL 的 join 功能也弱爆了，感興趣的同學(xué)可以了解一下這篇文章
而 ElasticSearch 則支持使用跳表 Skip List和 Bitset 的方式將數(shù)據(jù)集進(jìn)行合并。
使用 Skip List 結(jié)構(gòu)，同時(shí)遍歷 Score 和 Author 查詢出來(lái)的 Posting List，利用其 Skip List 結(jié)構(gòu)，相互跳躍對(duì)比，得出合集。
使用 Bitset 結(jié)構(gòu)，對(duì) Score 和 Author 查詢出來(lái)的 Posting List 的值計(jì)算出各自的 Bitset，然后進(jìn)行 AND 操作。
跳表合并策略
ElasticSearch 在存儲(chǔ) Posting List 數(shù)據(jù)時(shí)，就保存了對(duì)應(yīng)的多級(jí)跳表結(jié)構(gòu)響應(yīng)的數(shù)據(jù)，這也體現(xiàn)了其空間換時(shí)間的基本思想。
這里先介紹一下跳表的基本概念，它其實(shí)是一種可以進(jìn)行二分查找的有序鏈表。跳表在原有的有序鏈表上面增加了多級(jí)索引，通過(guò)索引來(lái)實(shí)現(xiàn)快速查找。首先在最高級(jí)索引上查找最后一個(gè)小于當(dāng)前查找元素的位置，然后再跳到次高級(jí)索引繼續(xù)查找，直到跳到最底層為止，通過(guò)這種方式，加快了查詢的速度。
比如，按照 Score 查出來(lái)的 Posting List 為[2,3,4,5,7,9,10,11]，按照 Author 查出來(lái)的結(jié)果為 [3,8,9,12,13]，則二者的跳表結(jié)構(gòu)如下圖所示。
具體合并過(guò)程則是先選最短的 posting list，也就是 Author 的結(jié)果集，從其最小的一個(gè) id 開(kāi)始，將其作為當(dāng)前最大值。然后依次剩余 posting list 中查找大于或等于該值的位置。
比如上述結(jié)果集中，先去 Score 結(jié)果集中查找 3，找到后，就表明 3是二者的合集元素之一；然后再重新開(kāi)啟一輪，選取 Author 結(jié)果集中 3 的下一個(gè)值 8 ，去 Score 結(jié)果集查詢 8，發(fā)現(xiàn)了大于等于 8 的最小的值是 9 ，所以不可能有共同的值 8，然后再去 Author 結(jié)果集查找 9 ，發(fā)現(xiàn)其大于等于 9 的最小值是 12，所以再去 Score 結(jié)果集中查找大于等于 12的值，發(fā)現(xiàn)并不存在；最終得出二者的合集就只有[3]。
在查詢過(guò)程中，每個(gè) posting list 都可以根據(jù)當(dāng)前 id 通過(guò) skip list 快速跳過(guò)不符合的 id 值，加速整個(gè)合并取交集的過(guò)程。
ElasticSearch 對(duì)于較長(zhǎng)的 posting list 也會(huì)使用 Frame Of Reference 進(jìn)行壓縮編碼，減少了磁盤占用，減少了索引尺寸。有關(guān)具體存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)我們后續(xù)再進(jìn)行細(xì)聊。
Bitset 合并策略
ElasticSearch除了使用 skipList 來(lái)進(jìn)行數(shù)據(jù)磁盤讀取時(shí)的合并操作外，還會(huì)將一些查詢條件對(duì)應(yīng)的結(jié)果集 posting list 進(jìn)行內(nèi)存緩存，也就是所謂的 Filter Cache，為了后續(xù)再次復(fù)用。
為了減少內(nèi)存緩存所消耗的內(nèi)存空間大小，ElasticSearch 沒(méi)有使用單純的數(shù)組和 bitset 來(lái)存儲(chǔ) posting list，而是使用要壓縮效率更高的 Roaring Bitmap。
我們可以先來(lái)講一下單純數(shù)組或 bitset 數(shù)據(jù)結(jié)構(gòu)為什么并不使用。比如如下一道較為常見(jiàn)的面試題目：
給定含有40億個(gè)不重復(fù)的位于[0, 2^32 - 1]區(qū)間內(nèi)的整數(shù)的集合，如何快速判定某個(gè)數(shù)是否在該集合內(nèi)？
如果我們要使用 unsigned long 數(shù)組來(lái)存儲(chǔ)它的話，也就需要消耗 40億 * 32 位 = 160 Byte，大致是 16000 MB。
如果要使用位圖 Bitset 來(lái)存儲(chǔ)的話，即某個(gè)數(shù)位于原集合內(nèi)，就將它對(duì)應(yīng)的位圖內(nèi)的比特置為1，否則保持為0。這樣只需要消耗 2 ^ 32 位 = 512 MB，這可只有原來(lái)的 3.2 % 左右。
但是，Bitset 也有其缺陷，也就是稀疏存儲(chǔ)的問(wèn)題，比如上述集合并不是 40億，而是只有2，3個(gè)，那么 Bitset 中只有少數(shù)幾位是1，其他位都是 0，但是它仍然占用了 512 MB。
而 RoaringBitmap 就是為了解決稀疏存儲(chǔ)的問(wèn)題。下圖就是 RoaringBitmap 的基本原理示意圖。
首先，如上圖所示，計(jì)算出32位無(wú)符號(hào)整數(shù)和 65536 的除數(shù)和余數(shù)。其含義表示，將32位無(wú)符號(hào)整數(shù)按照高16位分桶，即最多可能有2^16=65536個(gè)桶，術(shù)語(yǔ)懲治為 container。存儲(chǔ)數(shù)據(jù)時(shí)，按照數(shù)據(jù)的高16位找到 container（找不到就會(huì)新建一個(gè)），再將低16位放入container中。也就是說(shuō)，一個(gè) RoaringBitmap 就是很多container的集合。
然后 container 內(nèi)具體的存儲(chǔ)結(jié)構(gòu)要根據(jù)存入其內(nèi)數(shù)據(jù)的基數(shù)來(lái)決定。
基數(shù)小于 2 ^ 12 次方即 4096時(shí)，使用unsigned short類型的有序數(shù)組來(lái)存儲(chǔ)，最大消耗空間就是 8 KB。
基數(shù)大于 4096 時(shí)，則使用大小為 2 ^ 16 次方的普通 bitset 來(lái)存儲(chǔ)，固定消耗 8 KB。當(dāng)然，有些時(shí)候也會(huì)對(duì) bitset 進(jìn)行行程長(zhǎng)度編碼（RLE）壓縮，進(jìn)一步減少空間占用。
ElasticSearch 就是使用 Roaring Bitmap 來(lái)緩存不同條件查詢出來(lái)的 posting list，然后再進(jìn)行與操作計(jì)算出最終結(jié)果集。
后記
至此，我們也算了解了 ElasticSearch 為什么比 MySQL 更適合復(fù)雜條件查詢，但是有好就有弊，因?yàn)闉榱瞬樵冏隽诉@么多的準(zhǔn)備工作，ElasticSearch 的插入速度就會(huì)慢于 MySQL，而且數(shù)據(jù)存入ES后并不是立馬就能檢索到。
參考文章
http://www.nosqlnotes.com/technotes/searchengine/lucene-invertedindex/
https://zhuanlan.zhihu.com/p/33671444
https://www.cnblogs.com/forfuture1978/archive/2010/04/04/1704258.html
https://www.jianshu.com/p/818ac4e90daf
推薦閱讀：
IDEA 永久注冊(cè)碼來(lái)了?。。?/a> 分享5個(gè)免費(fèi)的在線 SQL 數(shù)據(jù)庫(kù)環(huán)境，簡(jiǎn)直太方便了！ 排名前 16 的 Java 工具類，哪個(gè)你沒(méi)用過(guò)的？ 推薦一款國(guó)產(chǎn)開(kāi)源監(jiān)控系統(tǒng)，太強(qiáng)大了??！ 如何實(shí)現(xiàn) MySQL 刪除重復(fù)記錄并且只保留一條？ 螞蟻金服開(kāi)源增強(qiáng)版 Spring Boot 的研發(fā)框架！
最近面試BAT，整理一份面試資料《Java面試BAT通關(guān)手冊(cè)》，覆蓋了Java核心技術(shù)、JVM、Java并發(fā)、SSM、微服務(wù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)結(jié)構(gòu)等等。 獲取方式：關(guān)注公眾號(hào)并回復(fù) java 領(lǐng)取，更多內(nèi)容陸續(xù)奉上。 明天見(jiàn)(??ω??)??