前言
這段時間在維護産品的搜尋功能，每次在管理台看到
elasticsearch
這麼高效的查詢效率我都很好奇他是如何做到的。
這甚至比在我本地使用
MySQL
通過主鍵的查詢速度還快。
為此我搜尋了相關資料：
這類問題網上很多答案，大概意思呢如下：
- ES 是基于
Lucene
MySQL
說的不是很透徹，沒有解析相關的原理；不過既然反複提到了索引，那我們就從索引的角度來對比下兩者的差異。
MySQL 索引
先從
MySQL
說起，索引這個詞想必大家也是爛熟于心，通常存在于一些查詢的場景，是典型的空間換時間的案例。
常見的資料結構
假設由我們自己來設計
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
反向索引的思路做一個單機版的搜尋引擎，隻有自己寫一遍才能加深了解。
你的點贊與在看是對我最大的支援~