前言

這段時間在維護產品的搜索功能，每次在管理臺看到 elasticsearch 這么高效的查詢效率我都很好奇他是如何做到的。

這甚至比在我本地使用 MySQL 通過主鍵的查詢速度還快。

為此我搜索了相關資料：

這類問題網上很多答案，大概意思呢如下：

•  ES 是基于 Lucene 的全文檢索引擎，它會對數據進行分詞后保存索引，擅長管理大量的索引數據，相對于 MySQL 來說不擅長經常更新數據及關聯查詢。

說的不是很透徹，沒有解析相關的原理；不過既然反復提到了索引，那我們就從索引的角度來對比下兩者的差異。

MySQL 索引

先從 MySQL 說起，索引這個詞想必大家也是爛熟于心，通常存在于一些查詢的場景，是典型的空間換時間的案例。

以下內容以 Innodb 引擎為例。

常見的數據結構

假設由我們自己來設計 MySQL 的索引，大概會有哪些選擇呢？

散列表

首先我們應當想到的是散列表，這是一個非常常見且高效的查詢、寫入的數據結構，對應到 Java 中就是 HashMap

這個數據結構應該不需要過多介紹了，它的寫入效率很高O(1),比如我們要查詢 id=3 的數據時，需要將 3 進行哈希運算，然后再這個數組中找到對應的位置即可。

但如果我們想查詢 1≤id≤6 這樣的區間數據時，散列表就不能很好的滿足了，由于它是無序的，所以得將所有數據遍歷一遍才能知道哪些數據屬于這個區間。

有序數組

有序數組的查詢效率也很高，當我們要查詢 id=4 的數據時，只需要通過二分查找也能高效定位到數據O(logn)。

同時由于數據也是有序的，所以自然也能支持區間查詢；這么看來有序數組適合用做索引咯?

自然是不行，它有另一個重大問題；假設我們插入了 id=2.5 的數據，就得同時將后續的所有數據都移動一位，這個寫入效率就會變得非常低。

平衡二叉樹

既然有序數組的寫入效率不高，那我們就來看看寫入效率高的，很容易就能想到二叉樹；這里我們以平衡二叉樹為例：

由于平衡二叉樹的特性：

左節點小于父節點、右節點大于父節點。

所以假設我們要查詢 id=11 的數據，只需要查詢 10—>12—>11 便能最終找到數據，時間復雜度為O(logn)，同理寫入數據時也為O(logn)。

但依然不能很好的支持區間范圍查找，假設我們要查詢5≤id≤20 的數據時，需要先查詢10節點的左子樹再查詢10節點的右子樹最終才能查詢到所有數據。

導致這樣的查詢效率并不高。

跳表

跳表可能不像上邊提到的散列表、有序數組、二叉樹那樣日常見的比較多，但其實 Redis 中的 sort set 就采用了跳表實現。

這里我們簡單介紹下跳表實現的數據結構有何優勢。

我們都知道即便是對一個有序鏈表進行查詢效率也不高，由于它不能使用數組下標進行二分查找，所以時間復雜度是o(n)

但我們也可以巧妙的優化鏈表來變相的實現二分查找，如下圖：

我們可以為最底層的數據提取出一級索引、二級索引，根據數據量的不同，我們可以提取出 N 級索引。

當我們查詢時便可以利用這里的索引變相的實現了二分查找。

假設現在要查詢 id=13 的數據，只需要遍歷 1—>7—>10—>13 四個節點便可以查詢到數據，當數越多時，效率提升會更明顯。

同時區間查詢也是支持，和剛才的查詢單個節點類似，只需要查詢到起始節點，然后依次往后遍歷（鏈表有序）到目標節點便能將整個范圍的數據查詢出來。

同時由于我們在索引上不會存儲真正的數據，只是存放一個指針，相對于最底層存放數據的鏈表來說占用的空間便可以忽略不計了。

平衡二叉樹的優化

但其實 MySQL 中的 Innodb 并沒有采用跳表，而是使用的一個叫做 B+ 樹的數據結構。

這個數據結構不像是二叉樹那樣大學老師當做基礎數據結構經常講到，由于這類數據結構都是在實際工程中根據需求場景在基礎數據結構中演化而來。

比如這里的 B+ 樹就可以認為是由平衡二叉樹演化而來。

剛才我們提到二叉樹的區間查詢效率不高，針對這一點便可進行優化：

在原有二叉樹的基礎上優化后：所有的非葉子都不存放數據，只是作為葉子節點的索引，數據全部都存放在葉子節點。

這樣所有葉子節點的數據都是有序存放的，便能很好的支持區間查詢。

只需要先通過查詢到起始節點的位置，然后在葉子節點中依次往后遍歷即可。

當數據量巨大時，很明顯索引文件是不能存放于內存中，雖然速度很快但消耗的資源也不小；所以 MySQL 會將索引文件直接存放于磁盤中。

這點和后文提到 elasticsearch 的索引略有不同。

由于索引存放于磁盤中，所以我們要盡可能的減少與磁盤的 IO（磁盤 IO 的效率與內存不在一個數量級）

通過上圖可以看出，我們要查詢一條數據至少得進行 4 次IO，很明顯這個 IO 次數是與樹的高度密切相關的，樹的高度越低 IO 次數就會越少，同時性能也會越好。

那怎樣才能降低樹的高度呢？

我們可以嘗試把二叉樹變為三叉樹，這樣樹的高度就會下降很多，這樣查詢數據時的 IO 次數自然也會降低，同時查詢效率也會提高許多。

這其實就是 B+ 樹的由來。

使用索引的一些建議

其實通過上圖對 B+樹的理解，也能優化日常工作的一些小細節；比如為什么需要最好是有序遞增的？

假設我們寫入的主鍵數據是無序的，那么有可能后寫入數據的 id 小于之前寫入的，這樣在維護 B+樹 索引時便有可能需要移動已經寫好數據。

如果是按照遞增寫入數據時則不會有這個考慮，每次只需要依次寫入即可。

所以我們才會要求數據庫主鍵盡量是趨勢遞增的，不考慮分表的情況時最合理的就是自增主鍵。

整體來看思路和跳表類似，只是針對使用場景做了相關的調整（比如數據全部存儲于葉子節點）。

ES 索引

MySQL 聊完了，現在來看看 Elasticsearch 是如何來使用索引的。

正排索引

在 ES 中采用的是一種名叫倒排索引的數據結構；在正式講倒排索引之前先來聊聊和他相反的正排索引。

以上圖為例，我們可以通過 doc_id 查詢到具體對象的方式稱為使用正排索引，其實也能理解為一種散列表。

本質是通過 key 來查找 value。

比如通過 doc_id=4 便能很快查詢到 name=jetty wang,age=20 這條數據。

倒排索引

那如果反過來我想查詢 name 中包含了 li 的數據有哪些？這樣如何高效查詢呢？

僅僅通過上文提到的正排索引顯然起不到什么作用，只能依次將所有數據遍歷后判斷名稱中是否包含 li ；這樣效率十分低下。

但如果我們重新構建一個索引結構：

當要查詢 name 中包含 li 的數據時，只需要通過這個索引結構查詢到 Posting List 中所包含的數據，再通過映射的方式查詢到最終的數據。

這個索引結構其實就是倒排索引。

Term Dictionary

但如何高效的在這個索引結構中查詢到 li 呢，結合我們之前的經驗，只要我們將 Term 有序排列，便可以使用二叉樹搜索樹的數據結構在o(logn) 下查詢到數據。

將一個文本拆分成一個一個獨立Term 的過程其實就是我們常說的分詞。

而將所有 Term 合并在一起就是一個 Term Dictionary，也可以叫做單詞詞典。

•  英文的分詞相對簡單，只需要通過空格、標點符號將文本分隔便能拆詞，中文則相對復雜，但也有許多開源工具做支持（由于不是本文重點，對分詞感興趣的可以自行搜索）。

當我們的文本量巨大時，分詞后的 Term 也會很多，這樣一個倒排索引的數據結構如果存放于內存那肯定是不夠存的，但如果像 MySQL 那樣存放于磁盤，效率也沒那么高。

Term Index

所以我們可以選擇一個折中的方法，既然無法將整個 Term Dictionary 放入內存中，那我們可以為Term Dictionary 創建一個索引然后放入內存中。

這樣便可以高效的查詢Term Dictionary ，最后再通過Term Dictionary 查詢到 Posting List。

相對于 MySQL 中的 B+樹來說也會減少了幾次磁盤IO。

這個 Term Index 我們可以使用這樣的 Trie樹 也就是我們常說的字典樹 來存放。

更多關于字典樹的內容請查看這里。

如果我們是以 j 開頭的 Term 進行搜索，首先第一步就是通過在內存中的 Term Index 查詢出以 j 打頭的 Term 在 Term Dictionary 字典文件中的哪個位置（這個位置可以是一個文件指針，可能是一個區間范圍）。

緊接著在將這個位置區間中的所有 Term 取出，由于已經排好序，便可通過二分查找快速定位到具體位置；這樣便可查詢出 Posting List。

最終通過 Posting List 中的位置信息便可在原始文件中將目標數據檢索出來。

更多優化

當然 ElasticSearch 還做了許多針對性的優化，當我們對兩個字段進行檢索時，就可以利用 bitmap 進行優化。

比如現在需要查詢 name=li and age=18 的數據，這時我們需要通過這兩個字段將各自的結果 Posting List 取出。

最簡單的方法是分別遍歷兩個集合，取出重復的數據，但這個明顯效率低下。

這時我們便可使用 bitmap 的方式進行存儲（還節省存儲空間），同時利用先天的位與 計算便可得出結果。

[1, 3, 5]       ⇒ 10101

[1, 2, 4, 5] ⇒ 11011

這樣兩個二進制數組求與便可得出結果：

10001 ⇒ [1, 5]

最終反解出 Posting List 為[1, 5],這樣的效率自然是要高上許多。

同樣的查詢需求在 MySQL 中并沒有特殊優化，只是先將數據量小的數據篩選出來之后再篩選第二個字段，效率自然也就沒有 ES 高。

當然在最新版的 ES 中也會對 Posting List 進行壓縮，具體壓縮規則可以查看官方文檔，這里就不具體介紹了。

總結

最后我們來總結一下：

通過以上內容可以看出再復雜的產品最終都是基礎數據結構組成，只是會對不同應用場景針對性的優化，所以打好數據結構與算法的基礎后再看某個新的技術或中間件時才能快速上手，甚至自己就能知道優化方向。

最后畫個餅，后續我會嘗試按照 ES 倒排索引的思路做一個單機版的搜索引擎，只有自己寫一遍才能加深理解。