目录
来源：ES 的倒排索引
现在有三段文本，id 分别是 0、1、2，你需要快速找到哪段文本里含有关键词"xiaobai".
I like xiaobai （点赞）
I follow xiaobai （关注）
I forward the video （转发）我们很容易想到，可以依次遍历这三段文本，匹配文本内是否含有"xiaobai"，最终将符合条件的文本 ID 输出。
在数据量小的时候，问题不大，但如果我有上百亿条这样的数据呢？
如果依次遍历，这一把执行下去，比你喜欢的女生回你消息的速度，还要慢。
像这种在海量数据中，通过关键词检索出有效信息的场景非常常见，比如我们网购用的某宝和某东的站内商品搜索。那么问题就来了，怎么处理类似的搜索场景呢？
好办，没有什么是加一层中间层不能解决的，如果有，那就再加一层。
这次我们要加的中间层是 elasticSearch。
什么是 elasticSearch。
elastic Search, 也就是 es，是一个开源的搜索引擎。
它介于应用和数据之间，只要将数据写入 es，应用就可以通过一些关键词搜索到数据。效果就像某度搜索一样。
那它是怎么做到的呢？我们从倒排索引聊起。
什么是倒排索引
回到文章开头的例子。依次遍历文本匹配是否含有"xiaobai"，确实低效。那有更高效的解法吗？有，我们可以对文本进行切分，比如"I like xiaobai"切分为"I"、"like"、"xiaobai"三部分，这个操作叫分词，分词后的每部分，我们称为一个词项，也就是 term。记录词项和文本 id 的关系，于是上面的三段文本就变成了下面这样。
term |
文本 id |
| I | 0, 1, 2 |
| like | 0 |
| xiaobai | 0, 1 |
| follow | 1 |
| forward | 2 |
| the | 2 |
| video | 2 |
当我们想要搜索 xiaobai 的时候，只需要匹配到 xiaobai 词项，就可以立马得到它所在的文档 id 是 0 和 1。但这有个问题，短短三句话，就已经有这么多词项了，要是换成三篇文档，那词项就会多得离谱，怎么在这么多的词项里匹配出 xiaobai 呢？挨个遍历的话，时间复杂度就是 O(N), 太低效了。
怎么办呢？我们可以将词项按字典序从小到大排序，通过二分查找的方法，直接将时间复杂度优化为 O(lgN)。就像下面这样。
| term | 文档 id |
| follow | 1 |
| forward | 2 |
| I | 0, 1, 2 |
| like | 0 |
| the | 2 |
| video | 2 |
| xiaobai | 0, 1 |
我们将这堆排好序的词项，称为Term Dictionary，而词项对应的文档 id 等信息的集合，就叫 Posting List。它们共同构成了一个用于搜索的数据结构，它就是**倒排索引(Inverted Index)**。
注意，Posting List 其实还包含词频和词项在文本里的偏移量等信息，但为了方便理解，我在上图中去掉了这部分内容。
但倒排索引还有个问题，Term Dictionary 数据量很大，放内存并不现实，因此必须放在磁盘中。但查询磁盘是个较慢的过程。有优化手段吗？有，我们聊下 Term Index。
Term Index 是什么
我们可以发现，词项和词项之间，有些前缀是一致的，比如 follow 和 forward 前面的 fo 是一致的，如果我们将部分 term 前缀提取出来，像下图一样，就可以用更少的空间表达更多的 term。基于这个原理，我们可以将 Term Dictionary 的部分词项提取出来