這篇文章主要介紹了MySQL索引 VS ElasticSearch索引的區(qū)別，具有一定借鑒價值，需要的朋友可以參考下。希望大家閱讀完這篇文章后大有收獲。下面讓小編帶著大家一起了解一下。
這段時間在維護產(chǎn)品的搜索功能，每次在管理臺看到 elasticsearch 這么高效的查詢效率我都很好奇他是如何做到的。
這甚至比在我本地使用 MySQL 通過主鍵的查詢速度還快。
為此我搜索了相關(guān)資料：
這類問題網(wǎng)上很多答案，大概意思呢如下：
重慶分公司
重慶分公司
Lucene 的全文檢索引擎，它會對數(shù)據(jù)進行分詞后保存索引，擅長管理大量的索引數(shù)據(jù)，相對于 MySQL 來說不擅長經(jīng)常更新數(shù)據(jù)及關(guān)聯(lián)查詢。說的不是很透徹，沒有解析相關(guān)的原理；不過既然反復(fù)提到了索引，那我們就從索引的角度來對比下兩者的差異。
先從 MySQL 說起，索引這個詞想必大家也是爛熟于心，通常存在于一些查詢的場景，是典型的空間換時間的案例。
以下內(nèi)容以 Innodb 引擎為例。復(fù)制代碼
假設(shè)由我們自己來設(shè)計 MySQL 的索引，大概會有哪些選擇呢？
首先我們應(yīng)當想到的是散列表，這是一個非常常見且高效的查詢、寫入的數(shù)據(jù)結(jié)構(gòu)，對應(yīng)到 Java 中就是 HashMap
這個數(shù)據(jù)結(jié)構(gòu)應(yīng)該不需要過多介紹了，它的寫入效率很高O(1),比如我們要查詢 id=3 的數(shù)據(jù)時，需要將 3 進行哈希運算，然后再這個數(shù)組中找到對應(yīng)的位置即可。
但如果我們想查詢 1≤id≤6 這樣的區(qū)間數(shù)據(jù)時，散列表就不能很好的滿足了，由于它是無序的，所以得將所有數(shù)據(jù)遍歷一遍才能知道哪些數(shù)據(jù)屬于這個區(qū)間。
有序數(shù)組的查詢效率也很高，當我們要查詢 id=4 的數(shù)據(jù)時，只需要通過二分查找也能高效定位到數(shù)據(jù)O(logn)。
同時由于數(shù)據(jù)也是有序的，所以自然也能支持區(qū)間查詢；這么看來有序數(shù)組適合用做索引咯?
自然是不行，它有另一個重大問題；假設(shè)我們插入了 id=2.5 的數(shù)據(jù)，就得同時將后續(xù)的所有數(shù)據(jù)都移動一位，這個寫入效率就會變得非常低。
既然有序數(shù)組的寫入效率不高，那我們就來看看寫入效率高的，很容易就能想到二叉樹；這里我們以平衡二叉樹為例：
由于平衡二叉樹的特性：
左節(jié)點小于父節(jié)點、右節(jié)點大于父節(jié)點。
所以假設(shè)我們要查詢 id=11 的數(shù)據(jù)，只需要查詢 10—>12—>11 便能最終找到數(shù)據(jù)，時間復(fù)雜度為O(logn)，同理寫入數(shù)據(jù)時也為O(logn)。
但依然不能很好的支持區(qū)間范圍查找，假設(shè)我們要查詢5≤id≤20 的數(shù)據(jù)時，需要先查詢10節(jié)點的左子樹再查詢10節(jié)點的右子樹最終才能查詢到所有數(shù)據(jù)。
導(dǎo)致這樣的查詢效率并不高。
跳表可能不像上邊提到的散列表、有序數(shù)組、二叉樹那樣日常見的比較多，但其實 Redis 中的 sort set 就采用了跳表實現(xiàn)。
這里我們簡單介紹下跳表實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)有何優(yōu)勢。
我們都知道即便是對一個有序鏈表進行查詢效率也不高，由于它不能使用數(shù)組下標進行二分查找，所以時間復(fù)雜度是o(n)
但我們也可以巧妙的優(yōu)化鏈表來變相的實現(xiàn)二分查找，如下圖：
我們可以為最底層的數(shù)據(jù)提取出一級索引、二級索引，根據(jù)數(shù)據(jù)量的不同，我們可以提取出 N 級索引。
當我們查詢時便可以利用這里的索引變相的實現(xiàn)了二分查找。
假設(shè)現(xiàn)在要查詢 id=13 的數(shù)據(jù)，只需要遍歷 1—>7—>10—>13 四個節(jié)點便可以查詢到數(shù)據(jù)，當數(shù)越多時，效率提升會更明顯。
同時區(qū)間查詢也是支持，和剛才的查詢單個節(jié)點類似，只需要查詢到起始節(jié)點，然后依次往后遍歷（鏈表有序）到目標節(jié)點便能將整個范圍的數(shù)據(jù)查詢出來。
同時由于我們在索引上不會存儲真正的數(shù)據(jù)，只是存放一個指針，相對于最底層存放數(shù)據(jù)的鏈表來說占用的空間便可以忽略不計了。
但其實 MySQL 中的 Innodb 并沒有采用跳表，而是使用的一個叫做 B+ 樹的數(shù)據(jù)結(jié)構(gòu)。
這個數(shù)據(jù)結(jié)構(gòu)不像是二叉樹那樣大學(xué)老師當做基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)經(jīng)常講到，由于這類數(shù)據(jù)結(jié)構(gòu)都是在實際工程中根據(jù)需求場景在基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)中演化而來。
比如這里的 B+ 樹就可以認為是由平衡二叉樹演化而來。
剛才我們提到二叉樹的區(qū)間查詢效率不高，針對這一點便可進行優(yōu)化：
在原有二叉樹的基礎(chǔ)上優(yōu)化后：所有的非葉子都不存放數(shù)據(jù)，只是作為葉子節(jié)點的索引，數(shù)據(jù)全部都存放在葉子節(jié)點。
這樣所有葉子節(jié)點的數(shù)據(jù)都是有序存放的，便能很好的支持區(qū)間查詢。
只需要先通過查詢到起始節(jié)點的位置，然后在葉子節(jié)點中依次往后遍歷即可。
當數(shù)據(jù)量巨大時，很明顯索引文件是不能存放于內(nèi)存中，雖然速度很快但消耗的資源也不?。凰?MySQL 會將索引文件直接存放于磁盤中。
這點和后文提到 elasticsearch 的索引略有不同。
由于索引存放于磁盤中，所以我們要盡可能的減少與磁盤的 IO（磁盤 IO 的效率與內(nèi)存不在一個數(shù)量級）
通過上圖可以看出，我們要查詢一條數(shù)據(jù)至少得進行 4 次IO，很明顯這個 IO 次數(shù)是與樹的高度密切相關(guān)的，樹的高度越低 IO 次數(shù)就會越少，同時性能也會越好。
那怎樣才能降低樹的高度呢？
我們可以嘗試把二叉樹變?yōu)槿鏄洌@樣樹的高度就會下降很多，這樣查詢數(shù)據(jù)時的 IO 次數(shù)自然也會降低，同時查詢效率也會提高許多。
這其實就是 B+ 樹的由來。
其實通過上圖對 B+樹的理解，也能優(yōu)化日常工作的一些小細節(jié)；比如為什么需要最好是有序遞增的？
假設(shè)我們寫入的主鍵數(shù)據(jù)是無序的，那么有可能后寫入數(shù)據(jù)的 id 小于之前寫入的，這樣在維護 B+樹 索引時便有可能需要移動已經(jīng)寫好數(shù)據(jù)。
如果是按照遞增寫入數(shù)據(jù)時則不會有這個考慮，每次只需要依次寫入即可。
所以我們才會要求數(shù)據(jù)庫主鍵盡量是趨勢遞增的，不考慮分表的情況時最合理的就是自增主鍵。
整體來看思路和跳表類似，只是針對使用場景做了相關(guān)的調(diào)整（比如數(shù)據(jù)全部存儲于葉子節(jié)點）。
MySQL 聊完了，現(xiàn)在來看看 Elasticsearch 是如何來使用索引的。
在 ES 中采用的是一種名叫倒排索引的數(shù)據(jù)結(jié)構(gòu)；在正式講倒排索引之前先來聊聊和他相反的正排索引。
以上圖為例，我們可以通過 doc_id 查詢到具體對象的方式稱為使用正排索引，其實也能理解為一種散列表。
本質(zhì)是通過 key 來查找 value。
比如通過 doc_id=4 便能很快查詢到 name=jetty wang,age=20 這條數(shù)據(jù)。
那如果反過來我想查詢 name 中包含了 li 的數(shù)據(jù)有哪些？這樣如何高效查詢呢？
僅僅通過上文提到的正排索引顯然起不到什么作用，只能依次將所有數(shù)據(jù)遍歷后判斷名稱中是否包含 li ；這樣效率十分低下。
但如果我們重新構(gòu)建一個索引結(jié)構(gòu)：
當要查詢 name 中包含 li 的數(shù)據(jù)時，只需要通過這個索引結(jié)構(gòu)查詢到 Posting List 中所包含的數(shù)據(jù)，再通過映射的方式查詢到最終的數(shù)據(jù)。
這個索引結(jié)構(gòu)其實就是倒排索引。
但如何高效的在這個索引結(jié)構(gòu)中查詢到 li 呢，結(jié)合我們之前的經(jīng)驗，只要我們將 Term 有序排列，便可以使用二叉樹搜索樹的數(shù)據(jù)結(jié)構(gòu)在o(logn) 下查詢到數(shù)據(jù)。
將一個文本拆分成一個一個獨立Term 的過程其實就是我們常說的分詞。
而將所有 Term 合并在一起就是一個 Term Dictionary，也可以叫做單詞詞典。
當我們的文本量巨大時，分詞后的 Term 也會很多，這樣一個倒排索引的數(shù)據(jù)結(jié)構(gòu)如果存放于內(nèi)存那肯定是不夠存的，但如果像 MySQL 那樣存放于磁盤，效率也沒那么高。
所以我們可以選擇一個折中的方法，既然無法將整個 Term Dictionary 放入內(nèi)存中，那我們可以為Term Dictionary 創(chuàng)建一個索引然后放入內(nèi)存中。
這樣便可以高效的查詢Term Dictionary ，最后再通過Term Dictionary 查詢到 Posting List。
相對于 MySQL 中的 B+樹來說也會減少了幾次磁盤IO。
這個 Term Index 我們可以使用這樣的 Trie樹 也就是我們常說的字典樹 來存放。
更多關(guān)于字典樹的內(nèi)容請查看這里。
如果我們是以 j 開頭的 Term 進行搜索，首先第一步就是通過在內(nèi)存中的 Term Index 查詢出以 j 打頭的 Term 在 Term Dictionary 字典文件中的哪個位置（這個位置可以是一個文件指針，可能是一個區(qū)間范圍）。
緊接著在將這個位置區(qū)間中的所有 Term 取出，由于已經(jīng)排好序，便可通過二分查找快速定位到具體位置；這樣便可查詢出 Posting List。
最終通過 Posting List 中的位置信息便可在原始文件中將目標數(shù)據(jù)檢索出來。
當然 ElasticSearch 還做了許多針對性的優(yōu)化，當我們對兩個字段進行檢索時，就可以利用 bitmap 進行優(yōu)化。
比如現(xiàn)在需要查詢 name=li and age=18 的數(shù)據(jù)，這時我們需要通過這兩個字段將各自的結(jié)果 Posting List 取出。
最簡單的方法是分別遍歷兩個集合，取出重復(fù)的數(shù)據(jù)，但這個明顯效率低下。
這時我們便可使用 bitmap 的方式進行存儲（還節(jié)省存儲空間），同時利用先天的位與 **計算便可得出結(jié)果。**
[1, 3, 5] ? 10101
[1, 2, 4, 5] ? 11011
這樣兩個二進制數(shù)組求與便可得出結(jié)果：
10001 ? [1, 5]
最終反解出 Posting List 為[1, 5],這樣的效率自然是要高上許多。
同樣的查詢需求在 MySQL 中并沒有特殊優(yōu)化，只是先將數(shù)據(jù)量小的數(shù)據(jù)篩選出來之后再篩選第二個字段，效率自然也就沒有 ES 高。
當然在最新版的 ES 中也會對 Posting List 進行壓縮，具體壓縮規(guī)則可以查看官方文檔，這里就不具體介紹了。
感謝你能夠認真閱讀完這篇文章，希望小編分享MySQL索引 VS ElasticSearch索引的區(qū)別內(nèi)容對大家有幫助，同時也希望大家多多支持創(chuàng)新互聯(lián)，關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司行業(yè)資訊頻道，遇到問題就找創(chuàng)新互聯(lián)，詳細的解決方法等著你來學(xué)習(xí)!
