Elasticsearch底层数据

基本概念

Elasticsearch是一个分布式全文检索系统。很多人说到它的特点：查询快，高吞吐量，可扩展。我们首先来看看它的底层数据结构。

底层数据

倒排索引(reverted index)

Elasticsearch依赖lucene来存储和索引数据。我们首先来看看它是如何处理数据。

用例：

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

我们有上面三句话。现在，我们要查询那句话包含了comming。

• 方案一：传统数据库
  有一个表t_content, 字段：id, content。所以我们查询的方式是： select * from t_content where content like '%coming%'
  因为content是一大段内容，我们是不能为其建立有效索引的。数据库查询，会将该表所有的行都扫描一把，拿其中的content与查询关键字来比较，这就是所谓的全表扫描。可以看到，这样的效率是非常的低效的。

• 方案二： Elasticsearch保存
  我们建立一个content的index, fields: id, content(text 类型)。当我们保存数据的时候，Elasticsearch首先会对content的内容进行词的拆分，最终建立content的索引， 这就是思维的倒排索引(reverted index)。

Term	Freq	Document
choice	1	3
coming	1	1
fury	1	2
is	3	1, 2, 3
ours	1	2
the	2	2, 3
winter	1	7
yours	1	3

如上图，我们可以看到lucene已经将content的内容拆分为词（term), 并统计它的使用的个数，在哪些document存在。
所以，当我们查询那句话包含了coming的时候，lucene首先在dictionary找到coming这个词，然后找到使用了它的document。（注: term dictionary）

总结：我们可以看到这两种查询方案，总结为两种不同的提问方式。

• 哪些文档包含了coming呢？遍历文档，看看每个文档是否包含了coming。
• coming在哪些文档中？ 事先为coming在哪些文档中建立索引，查找时候先找到coming对应的索引，再拿出对应的文档。

Lucene基本概念

• Term and Term dictionary: Term是Lucene中的最小的index单元，在某些内容的词法分析中产生（Analyzer/tokenizer)。Term dictionary是用来查询term的数据结构。

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

• Segment：Lucene的索引是由一系列的segments组成。每个segment是独立的且可以搜索。当创建index的时候：

  • 为新的document创建新的索引
  • 合并老的segment.

  查询的时候可能会涉及到多个segments.

• Document：类似数据库表的一行。

• Index：类似数据库表。

特点：

• Lucene在内存中建立索引，然后归集到segment, 写到磁盘
• segment是不可更改的，打一个删除的标记来删除
• segment使用一定的机制来定期merge
• 查询与搜索是基于segment

数据结构

• B+ 树

  
  B+.png

• Skip list

  
  skiplist.png

• FST（Finite State Transducer）

  • FST压缩率一般在3倍~20倍之间
  • O(len(str))的查询时间复杂度
  • Build FST

TF-IDF 关键词权重的度量

• TF 词频

  我们来看一个短语：美丽的燕子。它可以分为三个关键字：美丽，的，燕子。假如在两篇文章中，第一篇文章中出现的次数是5， 100， 5；在第二篇文章中出现的次数是8，100，5。我们可以认为搜索这个“美丽的燕子”时，第二篇的相关度比第一篇高。但是这里有个漏洞，假如第一篇文章的总字数为200，而第二篇的总字数为2000，明显文章长的占道便宜。

  TF（词频） = 关键字次数/总字数

  所以第一篇文章的词频分别为：0.025, 0.5, 0.025
  第二篇的词频分别为：0.004, 0.05, 0.0025

  有个简单的办法，就是直接使用关键字在文章中出现的总词频。对“美丽的燕子”，在第一篇总词频为：0.025 + 0.5 + 0.025 = 0.55， 在第二篇出现的总词频是：0.004 + 0.05 + 0.005 = 0.0475。

这里有个漏洞是：“的”，这个实际上是对相关性的区分是没有任何用处的，在实际的度量性中Lucene也不会进行处理。

• IDF(Inversted Document Frequent) 逆分档词频

  对“美丽的燕子”搜索，很明显“燕子”的关键性要大于“美丽”。“美丽”这个词太普遍了，可用于很多的地方。所以识别分类的时候，“燕子”的识别性更高。
  很容易发现，一个词在很少的文章中出现，那么它的分类型更强，可识别性更高，权重更大。相反，这个词在大多数的文章中存在，那么它的识别性更低，权重反而更小。

  IDF （逆文档词频） = log(D/Dw) D为出现的全部文档个数，Dw为改关键在在所有文档出现的次数。

  综上所述，TD-IDF = TF（词频） * IDF（逆文档词频）