Elasticsearch查詢速度這么快的原因是什么

這篇文章主要介紹“Elasticsearch查詢速度這么快的原因是什么”，在日常操作中，相信很多人在Elasticsearch查詢速度這么快的原因是什么問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”Elasticsearch查詢速度這么快的原因是什么”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！

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

為此我搜索了相關(guān)資料：

這類問題網(wǎng)上很多答案，大概意思呢如下：ES 是基于 Lucene 的全文檢索引擎，它會(huì)對(duì)數(shù)據(jù)進(jìn)行分詞后保存索引，擅長管理大量的索引數(shù)據(jù)，相對(duì)于 MySQL  來說不擅長經(jīng)常更新數(shù)據(jù)及關(guān)聯(lián)查詢。

說的不是很透徹，沒有解析相關(guān)的原理;不過既然反復(fù)提到了索引，那我們就從索引的角度來對(duì)比下兩者的差異。

MySQL 索引

先從 MySQL 說起，索引這個(gè)詞想必大家也是爛熟于心，通常存在于一些查詢的場(chǎng)景，是典型的空間換時(shí)間的案例。以下內(nèi)容以 InnoDB 引擎為例。

常見的數(shù)據(jù)結(jié)構(gòu)

假設(shè)由我們自己來設(shè)計(jì) MySQL 的索引，大概會(huì)有哪些選擇呢?

①散列表

首先我們應(yīng)當(dāng)想到的是散列表，這是一個(gè)非常常見且高效的查詢、寫入的數(shù)據(jù)結(jié)構(gòu)，對(duì)應(yīng)到 Java 中就是 HashMap。

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

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

②有序數(shù)組

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

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

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

③平衡二叉樹

既然有序數(shù)組的寫入效率不高，那我們就來看看寫入效率高的，很容易就能想到二叉樹。

這里我們以平衡二叉樹為例：

由于平衡二叉樹的特性：左節(jié)點(diǎn)小于父節(jié)點(diǎn)、右節(jié)點(diǎn)大于父節(jié)點(diǎn)。

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

但依然不能很好的支持區(qū)間范圍查找，假設(shè)我們要查詢 5≤id≤20 的數(shù)據(jù)時(shí)，需要先查詢 10 節(jié)點(diǎn)的左子樹再查詢 10  節(jié)點(diǎn)的右子樹最終才能查詢到所有數(shù)據(jù)。導(dǎo)致這樣的查詢效率并不高。

④跳表

跳表可能不像上邊提到的散列表、有序數(shù)組、二叉樹那樣日常見的比較多，但其實(shí) Redis 中的 sort set  就采用了跳表實(shí)現(xiàn)。這里我們簡(jiǎn)單介紹下跳表實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)有何優(yōu)勢(shì)。

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

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

我們可以為最底層的數(shù)據(jù)提取出一級(jí)索引、二級(jí)索引，根據(jù)數(shù)據(jù)量的不同，我們可以提取出 N  級(jí)索引。當(dāng)我們查詢時(shí)便可以利用這里的索引變相的實(shí)現(xiàn)了二分查找。

假設(shè)現(xiàn)在要查詢 id=13 的數(shù)據(jù)，只需要遍歷 1→7→10→13 四個(gè)節(jié)點(diǎn)便可以查詢到數(shù)據(jù)，當(dāng)數(shù)越多時(shí)，效率提升會(huì)更明顯。

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

同時(shí)由于我們?cè)谒饕喜粫?huì)存儲(chǔ)真正的數(shù)據(jù)，只是存放一個(gè)指針，相對(duì)于最底層存放數(shù)據(jù)的鏈表來說占用的空間便可以忽略不計(jì)了。

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

但其實(shí) MySQL 中的 InnoDB 并沒有采用跳表，而是使用的一個(gè)叫做 B+ 樹的數(shù)據(jù)結(jié)構(gòu)。

這個(gè)數(shù)據(jù)結(jié)構(gòu)不像是二叉樹那樣大學(xué)老師當(dāng)做基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)經(jīng)常講到，由于這類數(shù)據(jù)結(jié)構(gòu)都是在實(shí)際工程中根據(jù)需求場(chǎng)景在基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)中演化而來。

比如這里的 B+ 樹就可以認(rèn)為是由平衡二叉樹演化而來。剛才我們提到二叉樹的區(qū)間查詢效率不高，針對(duì)這一點(diǎn)便可進(jìn)行優(yōu)化：

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

這樣所有葉子節(jié)點(diǎn)的數(shù)據(jù)都是有序存放的，便能很好的支持區(qū)間查詢。只需要先通過查詢到起始節(jié)點(diǎn)的位置，然后在葉子節(jié)點(diǎn)中依次往后遍歷即可。

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

這點(diǎn)和后文提到 Elasticsearch 的索引略有不同。由于索引存放于磁盤中，所以我們要盡可能的減少與磁盤的 IO(磁盤 IO  的效率與內(nèi)存不在一個(gè)數(shù)量級(jí))。

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

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

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

使用索引的一些建議

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

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

如果是按照遞增寫入數(shù)據(jù)時(shí)則不會(huì)有這個(gè)考慮，每次只需要依次寫入即可。所以我們才會(huì)要求數(shù)據(jù)庫主鍵盡量是趨勢(shì)遞增的，不考慮分表的情況時(shí)最合理的就是自增主鍵。

整體來看思路和跳表類似，只是針對(duì)使用場(chǎng)景做了相關(guān)的調(diào)整(比如數(shù)據(jù)全部存儲(chǔ)于葉子節(jié)點(diǎn))。

ES 索引

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

正排索引

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

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

本質(zhì)是通過 key 來查找 value。比如通過 doc_id=4 便能很快查詢到 name=jetty wang，age=20 這條數(shù)據(jù)。

倒排索引

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

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

但如果我們重新構(gòu)建一個(gè)索引結(jié)構(gòu)：

當(dāng)要查詢 name 中包含 li 的數(shù)據(jù)時(shí)，只需要通過這個(gè)索引結(jié)構(gòu)查詢到 Posting List  中所包含的數(shù)據(jù)，再通過映射的方式查詢到最終的數(shù)據(jù)。

這個(gè)索引結(jié)構(gòu)其實(shí)就是倒排索引。

Term Dictionary

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

將一個(gè)文本拆分成一個(gè)一個(gè)獨(dú)立Term 的過程其實(shí)就是我們常說的分詞。

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

英文的分詞相對(duì)簡(jiǎn)單，只需要通過空格、標(biāo)點(diǎn)符號(hào)將文本分隔便能拆詞，中文則相對(duì)復(fù)雜，但也有許多開源工具做支持(由于不是本文重點(diǎn)，對(duì)分詞感興趣的可以自行搜索)。

當(dāng)我們的文本量巨大時(shí)，分詞后的 Term 也會(huì)很多，這樣一個(gè)倒排索引的數(shù)據(jù)結(jié)構(gòu)如果存放于內(nèi)存那肯定是不夠存的，但如果像 MySQL  那樣存放于磁盤，效率也沒那么高。

Term Index

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

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

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

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

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

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

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

更多優(yōu)化

當(dāng)然 Elasticsearch 還做了許多針對(duì)性的優(yōu)化，當(dāng)我們對(duì)兩個(gè)字段進(jìn)行檢索時(shí)，就可以利用 Bitmap 進(jìn)行優(yōu)化。

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

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

這時(shí)我們便可使用 Bitmap 的方式進(jìn)行存儲(chǔ)(還節(jié)省存儲(chǔ)空間)，同時(shí)利用先天的位與計(jì)算便可得出結(jié)果。

[1, 3, 5] ⇒ 10101  [1, 2, 4, 5] ⇒ 11011

這樣兩個(gè)二進(jìn)制數(shù)組求與便可得出結(jié)果：

10001 ⇒ [1, 5]

最終反解出 Posting List 為 [1, 5]，這樣的效率自然是要高上許多。同樣的查詢需求在 MySQL  中并沒有特殊優(yōu)化，只是先將數(shù)據(jù)量小的數(shù)據(jù)篩選出來之后再篩選第二個(gè)字段，效率自然也就沒有 ES 高。

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

總結(jié)

最后我們來總結(jié)一下：

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

到此，關(guān)于“Elasticsearch查詢速度這么快的原因是什么”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！