倒排索引_ 字节宝

倒排索引

编辑

倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件(inverted file)。

中文名

倒排索引

外文名

inverted index 构建方法

使用hash去重单词term

特殊要求

海量数据

概述

编辑

在关系数据库系统里，索引 [1] 是检索数据最有效率的方式,。但对于搜索引擎，它并不能满足其特殊要求：

1）海量数据：搜索引擎面对的是海量数据，像Google，百度这样大型的商业搜索引擎索引都是亿级甚至百亿级的网页数量，面对如此海量数据 ,使得数据库系统很难有效的管理。

2）数据操作简单：搜索引擎使用的数据操作简单 ,一般而言 ,只需要增、删、改、查几个功能 ,而且数据都有特定的格式 ,可以针对这些应用设计出简单高效的应用程序。而一般的数据库系统则支持大而全的功能 ,同时损失了速度和空间。最后 ,搜索引擎面临大量的用户检索需求 ,这要求搜索引擎在检索程序的设计上要分秒必争 ,尽可能的将大运算量的工作在索引建立时完成 ,使检索运算尽量的少。一般的数据库系统很难承受如此大量的用户请求 ,而且在检索响应时间和检索并发度上都不及我们专门设计的索引系统。

构建方法

编辑

简单法

索引的构建 [4] 相当于从正排表到倒排表的建立过程。当我们分析完网页时 ,得到的是以网页为主码的索引表。当索引建立完成后 ,应得到倒排表 ,具体流程如图所示：

流程描述如下：

1）将文档分析成单词term标记，

2）使用hash去重单词term 　　3）对单词生成倒排列表　　倒排列表就是文档编号DocID，没有包含其他的信息（如词频，单词位置等），这就是简单的索引。　　这个简单索引功能可以用于小数据，例如索引几千个文档。然而它有两点限制：　　1）需要有足够的内存来存储倒排表，对于搜索引擎来说，都是G级别数据，特别是当规模不断扩大时 ,我们根本不可能提供这么多的内存。　　2）算法是顺序执行，不便于并行处理。

合并法

归并法 [4] ,即每次将内存中数据写入磁盘时，包括词典在内的所有中间结果信息都被写入磁盘，这样内存所有内容都可以被清空，后续建立索引可以使用全部的定额内存。

归并索引

如图归并示意图：

合并流程：

1）页面分析，生成临时倒排数据索引A，B，当临时倒排数据索引A，B占满内存后，将内存索引A，B写入临时文件生成临时倒排文件，　　2) 对生成的多个临时倒排文件 ,执行多路归并 ,输出得到最终的倒排文件 ( inverted file)。

合并流程

索引创建过程中的页面分析 ,特别是中文分词为主要时间开销。算法的第二步相对很快。这样创建算法的优化集中在中文分词效率上。

更新策略

编辑

更新策略有四种 [2] ：完全重建、再合并策略、原地更新策略以及混合策略。

1. 完全重建策略：当新增文档到达一定数量，将新增文档和原先的老文档整合，然后利用静态索引创建方法对所有文档重建索引，新索引建立完成后老索引会被遗弃。此法代价高，但是主流商业搜索引擎一般是采用此方式来维护索引的更新（这句话是书中原话）
2. 再合并策略：当新增文档进入系统，解析文档，之后更新内存中维护的临时索引，文档中出现的每个单词，在其倒排表列表末尾追加倒排表列表项；一旦临时索引将指定内存消耗光，即进行一次索引合并，这里需要倒排文件里的倒排列表存放顺序已经按照索引单词字典顺序由低到高排序，这样直接顺序扫描合并即可。其缺点是：因为要生成新的倒排索引文件，所以对老索引中的很多单词，尽管其在倒排列表并未发生任何变化，也需要将其从老索引中取出来并写入新索引中，这样对磁盘消耗是没必要的。
3. 原地更新策略：试图改进再合并策略，在原地合并倒排表，这需要提前分配一定的空间给未来插入，如果提前分配的空间不够了需要迁移。实际显示，其索引更新的效率比再合并策略要低。
4. 混合策略：出发点是能够结合不同索引更新策略的长处，将不同索引更新策略混合，以形成更高效的方法。
5. https://baike.baidu.com/item/倒排索引/11001569?fr=aladdin

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/113134.html原文链接：https://javaforall.cn

搜索引擎存储 https 网络安全

0 人点赞

倒排索引

倒排索引

目录

概述

相关概念及定义

倒排列表

倒排索引

构建方法

简单法

合并法

更新策略