MySQL索引 VS ElasticSearch索引

今天MySQL資料庫欄位介紹MySQL索引與ElasticSearch索引的比較。

#前言

這段時間在維護產品的搜尋功能，每次在管理台看到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 倒排索引的思路做一個單機版的搜尋引擎，只有自己寫一遍才能加深理解。

相關免費學習推薦：mysql資料庫（影片）

#

以上是MySQL索引 VS ElasticSearch索引的詳細內容。更多資訊請關注PHP中文網其他相關文章！