网络百科 知识 倒排索引是什么意思

倒排索引是什么意思

倒排索引 : 一种用来迅速检索所有包含某个查询项的文档 的索引结构。对于每个查询项,在倒排文件中有包 含该项的文档列表(称为倒排列表)。以图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”的文档,可以以任意顺序读取两个查询 项的倒排列表,然后合并两个查询结果。

返回顶部