共计 1378 个字符，预计需要花费 4 分钟才能阅读完成。
Inverted Index
倒排索引（Inverted Index）是实现单词 - 文档矩阵的一种具体存储模式，在全文检索的场景中，能够实现疾速的搜寻需要，其由两局部形成，别离是 Term Dictionary、Posting List。
Term Dictionary
如下三个文档，文档 ID 别离是 001 和 002，每个文档中有一个字段，用来存储一段文本。
| ID | title |
|---|---|
| 001 | 金都嘉怡假日酒店 |
| 002 | 金都欣欣酒店 |
应用分词器对 title 进行分词，分词后果可能是这样
| ID | title | 分词后果 |
|---|---|---|
| 001 | 金都嘉怡假日酒店 | 金都，嘉怡，假日，酒店 |
| 002 | 金都欣欣酒店 | 金都，欣欣，酒店 |
去重分词后果，失去一个词语汇合：[金都，嘉怡，欣欣，假日，酒店]，这个词语汇合称之为词典，Term Dictionary 能够简略的认为就是这个词典。
词典是倒排索引中十分重要的组成部分，它用来保护文档汇合中所有的词语汇合，同时记录某个单词对应的 倒排列表 在倒排文件（存储倒排列表的文件）中的地位信息等。在反对搜寻时，依据用户的查问词，去词典里查问，就能够取得对应的倒排列表，并以此作为后续的排序的根底。
理论的利用场景中，Term Dictionary 是十分大的，搜索引擎须要实现疾速查找能力满足事实中的需要，那么就须要可能疾速的从词典中找到一个词语。为了可能满足疾速查找的需要，Term Dictionary 个别应用 B+ 树结构或者哈希 + 链表构造进行存储。
另外，为了节俭空间，Term Dictionary 在磁盘上是以分 Block 的形式保留的，一个 Block 外部利用公共前缀压缩，比方：将所有以“pre”结尾的单词提取“pre”作为公共局部，将残余局部原样保留，这样就能够节俭肯定的空间。
Posting List
倒排列表（Posting List）中记录了呈现过某个单词的所有文档的文档列表以及单词在该文档中呈现的次数、地位信息。上面联合倒排索引的残缺构造了解下倒排列表：
| 单词 ID | 单词 | 文档频率 | 倒排列表 |
|---|---|---|---|
| 1 | 金都 | 2 | (001;1;<1>), (002;1;<1>) |
| 2 | 嘉怡 | 2 | (001;1;<2>) |
| 3 | 欣欣 | 2 | (002;1;<2>) |
| 4 | 假日 | 2 | (001;1;<3>) |
| 5 | 酒店 | 2 | (001;1;<4>), (002;1;<3>) |
Term Index
实现全文检索的速度次要取决于词典查找的速度，尽管 Term Dictionary 应用了查找速度比拟高效的数据结构，然而还是防止不了磁盘随机拜访的性能影响，因为 Term Dictionary 比拟大，如果全副放入内存会有相当大的内存耗费，随着工夫，内存可能会被耗尽。所以 Term Dictionary 不适宜基于内存的查找。
为了进一步晋升 Term Dictionary 的查找速度，于是就有了 Term Index。Term index 应用的是 Trie 树结构。Trie 树不会蕴含所有的 Term，它仅蕴含的是 Term 的一些前缀。通过 Term Index 能够疾速地定位到 Term Dictionary 的 Block 地位，而后基于该 Block 依照 Term Dictionary 外部的数据结构进行查找。
Term Index 在内存中是以 FST（finite state transducers）的模式保留的，其特点是十分节俭内存，Term Index 的尺寸能够只有所有 Term 的尺寸的几十分之一，使得基于内存的词典查找变成可能。基于 Term Index 的查找流程如下图：
