前言

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

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

為此我搜索了相關資料：

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

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

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

MySQL 索引

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

以下內容以 Innodb 引擎為例。

常見的數(shù)據結構

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

散列表

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

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

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

有序數(shù)組

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

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

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

平衡二叉樹

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

由于平衡二叉樹的特性：

左節(jié)點小于父節(jié)點、右節(jié)點大于父節(jié)點。

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

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

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

跳表

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

這里我們簡單介紹下跳表實現(xiàn)的數(shù)據結構有何優(yōu)勢。

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

但我們也可以巧妙的優(yōu)化鏈表來變相的實現(xiàn)二分查找，如下圖：

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

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

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

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

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

平衡二叉樹的優(yōu)化

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

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

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

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

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

這樣所有葉子節(jié)點的數(shù)據都是有序存放的，便能很好的支持區(qū)間查詢。

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

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

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

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

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

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

我們可以嘗試把二叉樹變?yōu)槿鏄?，這樣樹的高度就會下降很多，這樣查詢數(shù)據時的 IO 次數(shù)自然也會降低，同時查詢效率也會提高許多。

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

使用索引的一些建議

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

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

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

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

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

ES 索引

MySQL 聊完了，現(xiàn)在來看看 Elasticsearch 是如何來使用索引的。

正排索引

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

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

本質是通過 key 來查找 value。

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

倒排索引

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

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

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

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

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

Term Dictionary

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

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

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

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

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

Term Index

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

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

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

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

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

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

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

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

更多優(yōu)化

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

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

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

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

[1, 3, 5]       ⇒ 10101

[1, 2, 4, 5] ⇒ 11011

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

10001 ⇒ [1, 5]

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

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

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

總結

最后我們來總結一下：

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

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