倒排索引
倒排索引由两部分构成：
- 单词词典
- 倒排列表
它的结构如下：
单词词典
单词词典的特性：
- 是文档集合中所有单词的集合
- 它是保存索引的最小单位
- 其中记录着指向倒排列表的指针
单词词典的实现：
单词词典有两种数据结构实现：B+树和Hash表
B+树和Mysql索引结构中主键索引数据结构一样，这里就不再介绍了
哈希表的key是单词的hash值，值是单词的链表，因为hash算法会有冲突的情况发生，所以这里的值是一个集合，里面保存着相同hash值得单词以及改词指向倒排列表的指针
倒排列表
倒排列表特性：
- 记录出现过某个单词的文档列表
- 同时还记录单词在所有文档中的出现次数和偏移位置
倒排列表元素数据结构：
其中：
- DocID：出现某单词的文档ID
- TF(Term Frequency)：单词在该文档中出现的次数
- POS：单词在文档中的位置
举例
有下面单个文档
| 内容 | |
|---|---|
| 文档1 | 百度的年度目标 |
| 文档2 | AI技术生态部的年度目标 |
| 文档3 | AI市场的年度目标 |
则他们生成的倒排索引
| 单词ID | 单词 | 逆向文档频率 | 倒排列表(DocID;TF;<POS>) |
|---|---|---|---|
| 1 | 目标 | 3 | (1;1;<3>),(2;1;<5>),(3;1;<4>) |
| 2 | 年度 | 3 | (1;1;<2>),(2;1;<4>),(3;1;<3>) |
| 3 | AI | 2 | (2;1;<1>),(3;1;<1>) |
| 4 | 技术 | 1 | (2;1;<2>) |
| 5 | 生态 | 1 | (2;1;<3>) |
| 6 | 市场 | 1 | (3;1;<2>) |
比如单词“年度”，单词ID为2，在三个文档中出现过，所以逆向文档频率为3，同时倒排索引中的元素也有三个：(1;1;<2>),(2;1;<4>),(3;1;<3>)。拿第一个元素(1;1;<2>)进行说明，他表示“年度”再文档ID为1的文档中出现过1次，出现的位置是第二个单词
倒排索引的搜索过程
直到了倒排索引的内部结构之后，就能很好理解倒排索引的搜索过程了，其内部搜索过程如下图所示：
网友评论