1 索引
1.1 什么是索引
索引是用于快速检索数据的一种数据结构。举个例子，新华字典的目录页就是典型的索引，可以通过目录查找对应汉字的详细数据，如果没有目录，那么每一个汉字都需要翻阅整个新华字典才能找到释义，太浪费时间了。
1.2 倒排索引能做什么
数据库索引通过索引列查询详细的数据，以下表为例。
| id | content |
|---|---|
| 1 | 我经常在美团上点外卖 |
| 2 | 我偶尔在饿了么上点外卖 |
| 3 | 外卖不如学校食堂好吃 |
| 4 | 我很少点商业街的外卖 |
数据库索引将id与title相关联，可以通过id搜索对应的title。但假如我需要查找content包含外卖的条目信息，那么在数据库索引中可以使用模糊查询%外卖%的方式，但我们知道这种查询方式会走全表扫描，效率低下。更进一步的，如果我想搜索美团外卖关键词呢。似乎btree索引无法实现这样的需求了。
因此，实际上倒排索引需要对文档内容进行分词。
| content | 分词结果 |
|---|---|
| 我常点美团的外卖 | 我、常点、美团、的、外卖 |
| 我常点饿了么的外卖 | 我、常点、饿了么、的、外卖 |
| 外卖不如学校食堂好吃 | 外卖、不如、学校、食堂、好吃 |
| 我不点商业街的外卖 | 我、不点、商业街、的、外卖 |
并且，每个分词都会跟对应的id关联起来。
| 分词 | 文档id |
|---|---|
| 我 | [1、2、4] |
| 常点 | [1、2] |
| 美团 | [1] |
| 饿了么 | [2] |
| 的 | [1、2、4] |
| 外卖 | [1、2、3、4] |
| 不如 | [3] |
| 学校 | [3] |
| … | … |
那么现在，如果想要查询外卖这个关键词，那么会首先拿到文档id1、2、3、4，然后通过id去搜索到具体的content内容。
如果想要查询外卖 美团这个关键词，那么会拿到文档id[1、2、3、4]与文档id[1]，然后做一个合并操作只留下文档id[1].再通过id搜索具体内容。
现在我们已经知道倒排索引的流程大致是什么样的了。但这里有几个问题仍然还没有明确：
- 分词是如何做的？
- 文档id的合并操作如何实现？
- 使用什么样的数据结构实现的倒排索引？
接下来的部分会对这几个问题进行阐述。
