倒排索引(数据库)
时间：2022-12-15 20:30:01 | 来源：信息时代
时间：2022-12-15 20:30:01 来源：信息时代
倒排索引 : 一种用来迅速检索所有包含某个查询项的文档的索引结构。对于每个查询项,在倒排文件中有包含该项的文档列表(称为倒排列表)。以图1中的文本数据库为例,查询项“James”相应的倒排列表为〈1,3,4〉,查询项“movie”的倒排列表为〈3,4〉。
| 记录标识 | 文档 | 签名 |
| 1 | agent James Bond | 1100 |
| 2 | agent mobile computer | 1101 |
| 3 | James Madison movie | 1011 |
| 4 | James Bond movie | 1110 |
| 单词 | 倒排列表 | Hash |
| agent | <1,2> | 1000 |
| Bond | <1,4> | 0100 |
| computer | <2> | 0100 |
| James | <1,3,4> | 1000 |
| Madison | <3> | 0001 |
| mobile | <2> | 0001 |
| movie | <3,4> | 0010 |
图1 包括4条记录和相应索引的文本数据库
图1中给出了所有查询项的倒排列表。为了迅速查找到某个查询项的倒排列表,需要为所有可能的查询项建立第二个索引结构、如B
+-树或Hash索引。为了避免混淆,我们把用来查找查询项的索引称为词表索引。词表索引由所有可能的查询项和指向相应倒排列表的指针组成。查询包含某个查询项的文档的过程如下。首先在词表索引中查找到对应该查询项倒排列表的结点,然后找到倒排列表,匹配记录标识和文档物理地址,最后检索到相应的文档。对于包含多个查询条件的查询,可以首先找到每个查询项的倒排列表,然后取它们的交集。为了尽量减少内存的占用,可以按照倒排列表的长度从小到大进行顺序抽取,由多个查询条件析取组成的查询,需要合并所有有关的倒排列表。
以图1中的文本数据库为例,查询包含“James”的文档,首先在词表索引中查找“James”的倒排列表,从磁盘中读出倒排列表,然后读出文档1。查询包含“James”和 “Bond”的文档,首先要检索到查询项“Bond”的倒排列表,与查询项“James”的倒排列表相交(查询项“Bond”的倒排列表长度为2,而查询项“James”的倒排列表长度为3)。列表〈1,4〉和列表〈1,3,4〉相交的结果是〈1,4〉,也就是检索到第一和第四个文档。要查询包含“James”或“Bond”的文档,可以以任意顺序读取两个查询项的倒排列表,然后合并两个查询结果。
在线咨询
