本文不會關注 ES 裡面的分散式技術、相關 API 的使用，而是專注分享下“ES 如何快速檢索”這個主題上面。這個也是我在學習之前對 ES 最感興趣的部分。

本文大致包括以下內容：

關於搜尋：

傳統關係型資料庫和 ES 的差別

搜尋引擎原理

細究倒排索引：

倒排索引具體是個什麼樣子的（posting list→term dic→term index）

關於 postings list 的一些巧技（FOR、Roaring Bitmaps）

如何快速做聯合查詢？

關於搜尋

先設想一個關於搜尋的場景，假設我們要搜尋一首詩句內容中帶“前”字的古詩。

用傳統關係型資料庫和 ES 實現會有什麼差別？如果用像 MySQL 這樣的 RDBMS 來儲存古詩的話，我們應該會去使用這樣的 SQL 去查詢：

這種我們稱為順序掃描法，需要遍歷所有的記錄進行匹配。不但效率低，而且不符合我們搜尋時的期望。

比如我們在搜尋“ABCD“這樣的關鍵詞時，通常還希望看到”A“，”AB“，”CD“，“ABC”的搜尋結果。於是乎就有了專業的搜尋引擎，比如我們今天的主角 ES。

搜尋引擎原理

搜尋引擎的搜尋原理簡單概括的話可以分為這麼幾步：

內容爬取，停頓詞過濾，比如一些無用的像”的“，“了”之類的語氣詞/連線詞

內容分詞，提取關鍵詞

根據關鍵詞建立倒排索引

使用者輸入關鍵詞進行搜尋

這裡我們就引出了一個概念，也是我們今天的要剖析的重點倒排索引。也是 ES 的核心知識點。

如果你瞭解 ES 應該知道，ES 可以說是對 Lucene 的一個封裝，裡面關於倒排索引的實現就是透過 lucene 這個 jar 包提供的 API 實現的，所以下面講的關於倒排索引的內容實際上都是 lucene 裡面的內容。

倒排索引

首先我們還不能忘了我們之前提的搜尋需求，先看下建立倒排索引之後，我們上述的查詢需求會變成什麼樣子。

這樣我們一輸入“前”，藉助倒排索引就可以直接定位到符合查詢條件的古詩。

當然這只是一個很大白話的形式來描述倒排索引的簡要工作原理。在 ES  中，這個倒排索引是具體是個什麼樣的，怎麼儲存的等等，這些才是倒排索引的精華內容。

①幾個概念

在進入下文之前，先描述幾個前置概念。

term：關鍵詞這個東西是我自己的講法，在 ES 中，關鍵詞被稱為 term。

postings list：還是用上面的例子，是 ”前“ 這個 term 所對應列表。在 ES 中，這些被描述為所有包含特定 term 文件的 id 的集合。

由於整型數字 integer 可以被高效壓縮的特質，integer 是最適合放在 postings list 作為文件的唯一標識的，ES 會對這些存入的文件進行處理，轉化成一個唯一的整型 id。

再說下這個 id 的範圍，在儲存資料的時候，在每一個 shard 裡面，ES 會將資料存入不同的 segment，這是一個比 shard 更小的分片單位，這些 segment 會定期合併。

在每一個 segment 裡面都會儲存最多 2^31 個文件，每個文件被分配一個唯一的 id，從 0 到 （2^31）-1。

相關的名詞都是 ES 官方文件給的描述，後面參考材料中都可以找到出處。

②索引內部結構

上面所描述的倒排索引，僅僅是一個很粗糙的模型。真的要在實際生產中使用，當然還差的很遠。

在實際生產場景中，比如 ES 最常用的日誌分析，日誌內容進行分詞之後，可以得到多少的 term？

那麼如何快速的在海量 term 中查詢到對應的 term 呢？遍歷一遍顯然是不現實的。

term dictionary：於是乎就有了 term dictionary，ES 為了能快速查詢到 term，將所有的 term 排了一個序，二分法查詢。

是不是感覺有點眼熟，這不就是 MySQL 的索引方式的，直接用 B+樹建立索引詞典指向被索引的資料。

term index：但是問題又來了，你覺得 Term Dictionary 應該放在哪裡？肯定是放在記憶體裡面吧？磁碟 io 那麼慢。就像 MySQL 索引就是存在記憶體裡面了。

但是如果把整個 term dictionary 放在記憶體裡面會有什麼後果呢？記憶體爆了…

別忘了，ES 預設可是會對全部 text 欄位進行索引，必然會消耗巨大的記憶體，為此 ES 針對索引進行了深度的最佳化。

在保證執行效率的同時，儘量縮減記憶體空間的佔用。於是乎就有了 term index。

Term index：從資料結構上分類算是一個“Trie 樹”，也就是我們常說的字典樹。

這是一種專門處理字串匹配的資料結構，用來解決在一組字串集合中快速查詢某個字串的問題。

這棵樹不會包含所有的 term，它包含的是 term 的一些字首（這也是字典樹的使用場景，公共字首）。

透過 term index 可以快速地定位到 term dictionary 的某個 offset，然後從這個位置再往後順序查詢。就想右邊這個圖所表示的。

怎麼樣，像不像我們查英文字典，我們定位 S 開頭的第一個單詞，或者定位到 Sh 開頭的第一個單詞，然後再往後順序查詢？

lucene 在這裡還做了兩點最佳化，一是 term dictionary 在磁碟上面是分 block 儲存的，一個 block 內部利用公共字首壓縮，比如都是 Ab 開頭的單詞就可以把 Ab 省去。

二是 term index 在記憶體中是以 FST（finite state transducers）的資料結構儲存的。

FST 有兩個優點：

空間佔用小：透過對詞典中單詞字首和字尾的重複利用，壓縮了儲存空間。

查詢速度快：O（len（str）） 的查詢時間複雜度。

FST 的理論比較複雜，本文不細講，延伸閱讀：https：//www。shenyanchao。cn/blog/2018/12/04/lucene-fst/

OK，現在我們能得到 lucene 倒排索引大致是個什麼樣子的了。

關於 postings list 的一些巧技

在實際使用中，postings list 還需要解決幾個痛點：

postings list 如果不進行壓縮，會非常佔用磁碟空間。

聯合查詢下，如何快速求交併集（intersections and unions）。

對於如何壓縮，可能會有人覺得沒有必要，”posting list 不是已經只儲存文件 id 了嗎？還需要壓縮？”，但是如果在 posting list 有百萬個 doc id 的情況，壓縮就顯得很有必要了。

比如按照朝代查詢古詩，至於為啥需要求交併集，ES 是專門用來搜尋的，肯定會有很多聯合查詢的需求吧 （AND、OR）。按照上面的思路，我們先將如何壓縮。

①壓縮

Frame of Reference：在 lucene 中，要求 postings lists 都要是有序的整形陣列。

這樣就帶來了一個很好的好處，可以透過 增量編碼（delta-encode）這種方式進行壓縮。

比如現在有 id 列表 ［73， 300， 302， 332， 343， 372］，轉化成每一個 id 相對於前一個 id 的增量值（第一個 id 的前一個 id 預設是 0，增量就是它自己）列表是 ［73， 227， 2， 30， 11， 29］。

在這個新的列表裡面，所有的 id 都是小於 255 的，所以每個 id 只需要一個位元組儲存。

實際上 ES 會做的更加精細：

它會把所有的文件分成很多個 block，每個 block 正好包含 256 個文件，然後單獨對每個文件進行增量編碼。

計算出儲存這個 block 裡面所有文件最多需要多少位來儲存每個 id，並且把這個位數作為頭資訊（header）放在每個 block 的前面。這個技術叫 Frame of Reference。

上圖也是來自於 ES 官方部落格中的一個示例（假設每個 block 只有 3 個檔案而不是 256）。

FOR 的步驟可以總結為：

進過最後的位壓縮之後，整型陣列的型別從固定大小（8，16，32，64 位）4 種類型，擴充套件到了 ［1-64］ 位共 64 種類型。

透過以上的方式可以極大的節省 posting list 的空間消耗，提高查詢效能。不過 ES 為了提高 filter 過濾器查詢的效能，還做了更多的工作，那就是快取。

Roaring Bitmaps （for filter cache）：在 ES 中，可以使用 filters 來最佳化查詢，filter 查詢只處理文件是否匹配與否，不涉及文件評分操作，查詢的結果可以被快取。

對於 filter 查詢，es 提供了 filter cache 這種特殊的快取，filter cache 用來儲存 filters 得到的結果集。

快取 filters 不需要太多的記憶體，它只保留一種資訊，即哪些文件與 filter 相匹配。同時它可以由其它的查詢複用，極大地提升了查詢的效能。

我們上面提到的 Frame Of Reference 壓縮演算法對於 postings list 來說效果很好，但對於需要儲存在記憶體中的 filter cache 等不太合適。

filter cache 會儲存那些經常使用的資料，針對 filter 的快取就是為了加速處理效率，對壓縮演算法要求更高。

對於這類 postings list，ES 採用不一樣的壓縮方式。那麼讓我們一步步來。首先我們知道 postings list 是 Integer 陣列，具有壓縮空間。

假設有這麼一個數組，我們第一個壓縮的思路是什麼？用位的方式來表示，每個文件對應其中的一位，也就是我們常說的點陣圖，bitmap。

它經常被作為索引用在資料庫、查詢引擎和搜尋引擎中，並且位操作（如 and 求交集、or 求並集）之間可以並行，效率更好。

但是，點陣圖有個很明顯的缺點，不管業務中實際的元素基數有多少，它佔用的記憶體空間都恆定不變。

也就是說不適用於稀疏儲存。業內對於稀疏點陣圖也有很多成熟的壓縮方案，lucene 採用的就是 roaring bitmaps。

我這裡用簡單的方式描述一下這個壓縮過程是怎麼樣：

將 doc id 拆成高 16 位，低 16 位。對高位進行聚合 （以高位做 key，value 為有相同高位的所有低位陣列），根據低位的資料量 （不同高位聚合出的低位陣列長度不相同），使用不同的 container（資料結構） 儲存。

len

len>=4096 BitmapContainer 使用 bitmap 儲存

分界線的來源：value 的最大總數是為2^16=65536。 假設以 bitmap 方式儲存需要 65536bit=8kb，而直接存值的方式，一個值 2 byte，4K 個總共需要2byte*4K=8kb。

所以當 value 總量

空間壓縮主要體現在：

高位聚合（假設資料中有 100w 個高位相同的值，原先需要 100w2byte，現在只要 12byte）

低位壓縮

缺點就在於位操作的速度相對於原生的 bitmap 會有影響。這就是 trade-off 呀。平衡的藝術。

②聯合查詢

講完了壓縮，我們再來講講聯合查詢。先講簡單的，如果查詢有 filter cache，那就是直接拿 filter cache 來做計算，也就是說點陣圖來做 AND 或者 OR 的計算。

如果查詢的 filter 沒有快取，那麼就用 skip list 的方式去遍歷磁碟上的 postings list。

以上是三個 posting list。我們現在需要把它們用 AND 的關係合併，得出 posting list 的交集。

首先選擇最短的 posting list，逐個在另外兩個 posting list 中查詢看是否存在，最後得到交集的結果。

遍歷的過程可以跳過一些元素，比如我們遍歷到綠色的 13 的時候，就可以跳過藍色的 3 了，因為 3 比 13 要小。

用 skip list 還會帶來一個好處，還記得前面說的嗎，postings list 在磁盤裡面是採用 FOR 的編碼方式儲存的。

會把所有的文件分成很多個 block，每個 block 正好包含 256 個文件，然後單獨對每個文件進行增量編碼，計算出儲存這個 block 裡面所有文件最多需要多少位來儲存每個 id，並且把這個位數作為頭資訊（header）放在每個 block 的前面。

因為這個 FOR 的編碼是有解壓縮成本的。利用 skip list，除了跳過了遍歷的成本，也跳過了解壓縮這些壓縮過的 block 的過程，從而節省了 cpu。

總結

下面我們來做一個技術總結：

①為了能夠快速定位到目標文件，ES 使用倒排索引技術來最佳化搜尋速度，雖然空間消耗比較大，但是搜尋效能提高十分顯著。

②為了能夠在數量巨大的 terms 中快速定位到某一個 term，同時節約對記憶體的使用和減少磁碟 io 的讀取。

lucene 使用 ”term index→term dictionary→postings list“ 的倒排索引結構，透過 FST 壓縮放入記憶體，進一步提高搜尋效率。

③為了減少  postings list 的磁碟消耗，lucene 使用了 FOR（Frame of Reference）技術壓縮，帶來的壓縮效果十分明顯。

④ES 的 filter 語句採用了 Roaring Bitmap 技術來快取搜尋結果，保證高頻 filter 查詢速度的同時降低儲存空間消耗。

⑤在聯合查詢時，在有 filter cache 的情況下，會直接利用點陣圖的原生特性快速求交併集得到聯合查詢結果，否則使用 skip list 對多個 postings list 求交併集，跳過遍歷成本並且節省部分資料的解壓縮 cpu 成本。

Elasticsearch 的索引思路

將磁盤裡的東西儘量搬進記憶體，減少磁碟隨機讀取次數 （同時也利用磁碟順序讀特性），結合各種壓縮演算法，用及其苛刻的態度使用記憶體。

所以，對於使用 Elasticsearch 進行索引時需要注意：

不需要索引的欄位，一定要明確定義出來，因為預設是自動建索引的。

同樣的道理，對於 String 型別的欄位，不需要 analysis 的也需要明確定義出來，因為預設也是會 analysis 的。

選擇有規律的 ID 很重要，隨機性太大的 ID（比如 Java 的 UUID） 不利於查詢。

最後說一下，技術選型永遠伴隨著業務場景的考量，每種資料庫都有自己要解決的問題（或者說擅長的領域），對應的就有自己的資料結構，而不同的使用場景和資料結構，需要用不同的索引，才能起到最大化加快查詢的目的。

這篇文章講的雖是 Lucene 如何實現倒排索引，如何精打細算每一塊記憶體、磁碟空間、如何用詭譎的位運算加快處理速度。

但往高處思考，再類比一下 MySQL，你就會發現，雖然都是索引，但是實現起來，截然不同。籠統的來說，B-tree 索引是為寫入最佳化的索引結構。

當我們不需要支援快速的更新的時候，可以用預先排序等方式換取更小的儲存空間，更快的檢索速度等好處，其代價就是更新慢，就像 ES。

呂大師精心打造深度培訓課程

（限時特惠價格128元）

課程：借鑑 Oracle，深入修改 MySQL/PostgreSQL 核心程式碼——-PG篇

ITPUB使用者福利掃碼領取免費基礎課（基礎課每週都會有更新哦）：

①巧解妙用解讀資料庫的CheckPoint（檢查點）

②拒絕躺平——資料庫原始碼閱讀技巧解析

③記憶體是什麼（一）

④記憶體是什麼（二）

你

「在看」嗎？