基本概念
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（逆文档词频）
