Elasticsearch核心技術與實戰學習筆記 第三章12 反向索引介紹

一 序

  本文屬于極客時間Elasticsearch核心技術與實戰學習筆記系列。

 本節純講理論的，如果了解過反向索引的可以跳過。

二 相關閱讀

先說下我自己的了解，不一定準确。錯誤之處歡迎指正。

  一說到索引肯定會想起MySQL的索引。就是有關索引的目的：為了快速查找到你要的資料。

MySQL的B+索引，是為了讀優化的。有序性等特征适合的業務場景不是複雜查詢。

我們可以想下，涉及到反向索引的場景就是根據單詞去找文檔的，這個量很大，不能吧所有索引資料都放到記憶體。那es怎麼實作？infoq上有篇文章講的不錯。為了便于了解截取部分：原文：https://www.infoq.cn/article/database-timestamp-02/

假設有如下的資料：

這裡每一行是一個document。每個document都有一個docid。那麼給這些document建立的反向索引就是：

可以看到，反向索引是per field的，一個字段由一個自己的反向索引。18,20這些叫做 term，而[1,3]就是posting list。Posting list就是一個int的數組，存儲了所有符合某個term的文檔id。那麼什麼是term dictionary 和 term index？

假設我們有很多個term，比如：

Carla,Sara,Elin,Ada,Patty,Kate,Selena

如果按照這樣的順序排列，找出某個特定的term一定很慢，因為term沒有排序，需要全部過濾一遍才能找出特定的term。排序之後就變成了：

Ada,Carla,Elin,Kate,Patty,Sara,Selena

這樣我們可以用二分查找的方式，比全周遊更快地找出目标的term。這個就是 term dictionary。有了term dictionary之後，可以用 logN 次磁盤查找得到目标。但是磁盤的随機讀操作仍然是非常昂貴的（一次random access大概需要10ms的時間）。是以盡量少的讀磁盤，有必要把一些資料緩存到記憶體裡。但是整個term dictionary本身又太大了，無法完整地放到記憶體裡。于是就有了term index。term index有點像一本字典的大的章節表。比如：

A開頭的term ……………. Xxx頁

C開頭的term ……………. Xxx頁

E開頭的term ……………. Xxx頁

如果所有的term都是英文字元的話，可能這個term index就真的是26個英文字元表構成的了。但是實際的情況是，term未必都是英文字元，term可以是任意的byte數組。而且26個英文字元也未必是每一個字元都有均等的term，比如x字元開頭的term可能一個都沒有，而s開頭的term又特别多。實際的term index是一棵trie 樹：

例子是一個包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的 trie 樹。這棵樹不會包含所有的term，它包含的是term的一些字首。通過term index可以快速地定位到term dictionary的某個offset，然後從這個位置再往後順序查找。再加上一些壓縮技術（搜尋 Lucene Finite State Transducers） term index 的尺寸可以隻有所有term的尺寸的幾十分之一，使得用記憶體緩存整個term index變成可能。整體上來說就是這樣的效果。

現在我們可以回答“為什麼Elasticsearch/Lucene檢索可以比mysql快了。Mysql隻有term dictionary這一層，是以b-tree排序的方式存儲在磁盤上的。檢索一個term需要若幹次的random access的磁盤操作。而Lucene在term dictionary的基礎上添加了term index來加速檢索，term index以樹的形式緩存在記憶體中。從term index查到對應的term dictionary的block位置之後，再去磁盤上找term，大大減少了磁盤的random access次數。

額外值得一提的兩點是：term index在記憶體中是以FST（finite state transducers）的形式儲存的，其特點是非常節省記憶體。Term dictionary在磁盤上是以分block的方式儲存的，一個block内部利用公共字首壓縮，比如都是Ab開頭的單詞就可以把Ab省去。這樣term dictionary可以比b-tree更節約磁盤空間。

好了，有些這些背景知識做鋪墊。你再聽老師講就清晰多了。

三 關鍵資訊

老師講這塊的時候用了圖書的目錄索引做例子介紹。

• 正排索引-文檔 Id 到文檔内容和單詞的關聯
• 反向索引-單詞到文檔 Id 的關系

反向索引表三列：單詞，次數，文檔ID和位置。

• 反向索引包含兩部分：單詞詞典（Team Dictionary）和倒排清單（Posting List）
• 單詞詞典記錄單詞到倒排清單的關聯關系，一般通過 B+ 樹或者哈希連結清單實作
• 倒排清單記錄單詞對應的文檔結合，由反向索引項組成
• 反向索引項由文檔ID(docId)，詞頻（term frequencies），單詞位置(term postion)，偏移量(character offsets)組成

ES 也可以指定對某些字段不做索引

• 優點：節省存儲空間
• 缺點：字段無法被搜尋

小結

要了解反向索引與正排索引的差別，  Elasticsearch 中資料索引過程的流程：

    從文檔-->分詞-->term->index. 

你隻能搜尋在索引中出現的詞條，是以索引文本和查詢字元串必須标準化為相同的格式。分詞和标準化的過程稱為分析，下一節課講。