基本概念

Elasticsearch是一個分布式全文檢索系統(tǒng)。很多人說到它的特點：查詢快，高吞吐量，可擴展。我們首先來看看它的底層數(shù)據(jù)結(jié)構(gòu)。

底層數(shù)據(jù)

倒排索引(reverted index)

Elasticsearch依賴lucene來存儲和索引數(shù)據(jù)。我們首先來看看它是如何處理數(shù)據(jù)。

用例：

• Winter is coming
• Ours is the fory
• The choice is yours

我們有上面三句話?，F(xiàn)在，我們要查詢那句話包含了comming。

• 方案一：傳統(tǒng)數(shù)據(jù)庫
  有一個表t_content, 字段：id, content。所以我們查詢的方式是： select * from t_content where content like '%coming%'
  因為content是一大段內(nèi)容，我們是不能為其建立有效索引的。數(shù)據(jù)庫查詢，會將該表所有的行都掃描一把，拿其中的content與查詢關(guān)鍵字來比較，這就是所謂的全表掃描?？梢钥吹剑@樣的效率是非常的低效的。

• 方案二： Elasticsearch保存
  我們建立一個content的index, fields: id, content(text 類型)。當(dāng)我們保存數(shù)據(jù)的時候，Elasticsearch首先會對content的內(nèi)容進行詞的拆分，最終建立content的索引， 這就是思維的倒排索引(reverted index)。

如上圖，我們可以看到lucene已經(jīng)將content的內(nèi)容拆分為詞（term), 并統(tǒng)計它的使用的個數(shù)，在哪些document存在。
所以，當(dāng)我們查詢那句話包含了coming的時候，lucene首先在dictionary找到coming這個詞，然后找到使用了它的document。（注: term dictionary）

總結(jié)：我們可以看到這兩種查詢方案，總結(jié)為兩種不同的提問方式。

• 哪些文檔包含了coming呢？遍歷文檔，看看每個文檔是否包含了coming。
• coming在哪些文檔中？ 事先為coming在哪些文檔中建立索引，查找時候先找到coming對應(yīng)的索引，再拿出對應(yīng)的文檔。

Lucene基本概念

• Term and Term dictionary: Term是Lucene中的最小的index單元，在某些內(nèi)容的詞法分析中產(chǎn)生（Analyzer/tokenizer)。Term dictionary是用來查詢term的數(shù)據(jù)結(jié)構(gòu)。

• Field： 一個document可能包含許多fields。列如：一個BLOG可能包括author, title, content, publish date。Lucene為不同的field提供了不同的類型, 比如：keyword, text, long, date等。

• Segment：Lucene的索引是由一系列的segments組成。每個segment是獨立的且可以搜索。當(dāng)創(chuàng)建index的時候：

  • 為新的document創(chuàng)建新的索引
  • 合并老的segment.

  查詢的時候可能會涉及到多個segments.

• Document：類似數(shù)據(jù)庫表的一行。

• Index：類似數(shù)據(jù)庫表。

特點：

• Lucene在內(nèi)存中建立索引，然后歸集到segment, 寫到磁盤
• segment是不可更改的，打一個刪除的標(biāo)記來刪除
• segment使用一定的機制來定期merge
• 查詢與搜索是基于segment

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

• B+ 樹

  
  
  B+.png

• Skip list

  
  
  skiplist.png

• FST（Finite State Transducer）

  • FST壓縮率一般在3倍~20倍之間
  • O(len(str))的查詢時間復(fù)雜度
  • Build FST

TF-IDF 關(guān)鍵詞權(quán)重的度量

• TF 詞頻

  我們來看一個短語：美麗的燕子。它可以分為三個關(guān)鍵字：美麗，的，燕子。假如在兩篇文章中，第一篇文章中出現(xiàn)的次數(shù)是5， 100， 5；在第二篇文章中出現(xiàn)的次數(shù)是8，100，5。我們可以認(rèn)為搜索這個“美麗的燕子”時，第二篇的相關(guān)度比第一篇高。但是這里有個漏洞，假如第一篇文章的總字?jǐn)?shù)為200，而第二篇的總字?jǐn)?shù)為2000，明顯文章長的占道便宜。

  TF（詞頻） = 關(guān)鍵字次數(shù)/總字?jǐn)?shù)

  所以第一篇文章的詞頻分別為：0.025, 0.5, 0.025
  第二篇的詞頻分別為：0.004, 0.05, 0.0025

  有個簡單的辦法，就是直接使用關(guān)鍵字在文章中出現(xiàn)的總詞頻。對“美麗的燕子”，在第一篇總詞頻為：0.025 + 0.5 + 0.025 = 0.55， 在第二篇出現(xiàn)的總詞頻是：0.004 + 0.05 + 0.005 = 0.0475。

這里有個漏洞是：“的”，這個實際上是對相關(guān)性的區(qū)分是沒有任何用處的，在實際的度量性中Lucene也不會進行處理。

• IDF(Inversted Document Frequent) 逆分檔詞頻

  對“美麗的燕子”搜索，很明顯“燕子”的關(guān)鍵性要大于“美麗”。“美麗”這個詞太普遍了，可用于很多的地方。所以識別分類的時候，“燕子”的識別性更高。
  很容易發(fā)現(xiàn)，一個詞在很少的文章中出現(xiàn)，那么它的分類型更強，可識別性更高，權(quán)重更大。相反，這個詞在大多數(shù)的文章中存在，那么它的識別性更低，權(quán)重反而更小。

  IDF （逆文檔詞頻） = log(D/Dw) D為出現(xiàn)的全部文檔個數(shù)，Dw為改關(guān)鍵在在所有文檔出現(xiàn)的次數(shù)。

  綜上所述，TD-IDF = TF（詞頻） * IDF（逆文檔詞頻）