跳表法加速倒排索引

简介: 跳表、哈希表与位图法可加速倒排索引。跳表通过多层链表实现快速跳转,将归并查找时间降至O(log n);哈希表适用于小集合查大集合,查询可达O(1);位图则利用位运算高效求交集,适合短posting list场景,显著提升检索效率。

跳表法加速倒排索引

在 第 5 讲 中我们讲过,倒排索引中的 posting list 一般是用链表来实现的。当两个 posting list A 和 B 需要合并求交集时,如果我们用归并法来合并的话,时间代价是 O(m+n)。其中,m 为 posting list A 的长度,n 为 posting list B 的长度。

那对于这个归并过程,工业界是如何优化的呢?接下来,我们就通过一个例子来看一下。

假设 posting list A 中的元素为 <1,2,3,4,5,6,7,8……,1000> ,这 1000 个元素是按照从 1 到 1000 的顺序递增的。而 posting list B 中的元素,只有 <1,500,1000> 3 个。那按照我们之前讲过的归并方法,它们的合并过程就是,在找到相同元素 1 以后,还需要再遍历 498 次链表,才能找到第二个相同元素 500。

需要顺序遍历498次链表A31000502500501503key1链表B1000500key2

链表遍历,时间代价高

很显然,为了找到一个元素,遍历这么多次是很不划算的。那对于链表遍历,我们可以怎么优化呢?实际上,在许多工业界的实践中,比如搜索引擎,还有 Lucene 和 Elasticsearch 等应用中,都是使用跳表来实现 posting list 的。

在上面这个例子中,我们可以将链表改为跳表。这样,在 posting list A 中,我们从第 2 个元素遍历到第 500 个元素,只需要 log(498) 次的量级,会比链表快得多。
跳表优化,只需查找log(n)次链表A5025001000501503key1链表B1000500key2

跳表查找,检索加速

这个时候你可能就会问了,我们只能用 B 中的每一个元素去 A 中二分查找吗?那在解答这个问题之前,我们先来看下图这个例子。
链表A3500key11000链表B5035011000502key2500

相互二分查找
你会发现,在寻找 500 这个公共元素的过程中,我们是拿着链表 B 中的 500 作为 key,在链表 A 中进行跳表二分查找的。但是,在查找 1000 这个公共元素的过程中,我们是拿着链表 A 中的元素 1000,在链表 B 中进行跳表二分查找的。

我们把这种方法定义为 相互二分查找。那啥叫相互二分查找呢?

你可以这么理解:如果 A 中的当前元素小于 B 中的当前元素,我们就以 B 中的当前元素为 key,在 A 中快速往前跳;如果 B 中的当前元素小于 A 中的当前元素,我们就以 A 中的当前元素为 key,在 B 中快速往前跳。这样一来,整体的检索效率就提升了。

在实际的系统中,如果 posting list 可以都存储在内存中,并且变化不太频繁的话,那我们还可以利用 可变长数组 来代替链表。

可变长数组的数组的长度可以随着数据的增加而增加。一种简单的可变长数组实现方案就是当数组被写满时,我们直接重新申请一个 2 倍于原数组的新数组,将原数组数据直接导入新数组中。这样,我们就可以应对数据动态增长的场景。

那对于两个 posting list 求交集,我们同样可以先使用可变长数组,再利用 相互二分查找 进行归并。而且,由于数组的数据在内存的物理空间中是紧凑的,因此 CPU 还可以利用内存的局部性原理来提高检索效率。

哈希表法加速倒排索引

说到高效查询,哈希表 O(1) 级别的查找能力令人印象深刻。那我们有没有能利用哈希表来加速的方法呢?别说,还真有。

哈希表加速的思路其实很简单,就是当两个集合要求交集时,如果一个集合特别大,另一个集合相对比较小,那我们就可以用哈希表来存储大集合。这样,我们就可以拿着小集合中的每一个元素去哈希表中对比:如果查找为存在,那查找的元素就是公共元素;否则,就放弃。

我们还是以前面说的 posting list A 和 B 为例,来进一步解释一下这个过程。由于 Posting list A 有 1000 个元素,而 B 中只有 3 个元素,因此,我们可以将 posting list A 中的元素提前存入哈希表。这样,我们利用 B 中的 3 个元素来查询的时候,每次查询代价都是 O(1)。如果 B 有 m 个元素,那查询代价就是 O(m)。

链表A25035015025001000key1哈希表A链表B1000500key2

将 posting list A 中的元素提前存入哈希表
但是,使用哈希表法加速倒排索引有一个前提,就是我们要在 查询发生之前,就把 posting list 转为哈希表。这就需要我们提前分析好,哪些 posting list 经常会被拿来求交集,针对这一批 posting list,我们将它们提前存入哈希表。这样,我们就能实现检索加速了。

这里还有一点需要你注意,原始的 posting list 我们也要保留。这是为什么呢?

我们假设有这样一种情况:当我们要给两个 posting list 求交集时,发现这两个 posting list 都已经转为哈希表了。这个时候,由于哈希表没有遍历能力,反而会导致我们无法合并这两个 posting list。因此,在哈希表法的最终改造中,一个 key 后面会有两个指针,一个指向 posting list,另一个指向哈希表(如果哈希表存在)。

除此之外,哈希表法还需要在有很多短 posting list 存在的前提下,才能更好地发挥作用。这是因为哈希表法的查询代价是 O(m),如果 m 的值很大,那它的性能就不一定会比跳表法更优了。

位图法加速倒排索引

我们知道,位图其实也可以看作是一种特殊的哈希,所以除了哈希表,我们还可以使用位图法来改造链表。如果我们使用位图法,就需要将所有的 posting list 全部改造为位图,这样才能使用位图的位运算来进行检索加速。那具体应该怎么做呢?我们一起来看一下。

首先,我们需要为每个 key 生成同样长度的位图,表示所有的对象空间。然后,如果一个元素出现在该 posting list 中,我们就将位图中该元素对应的位置置为 1。这样就完成了 posting list 的位图改造。

接下来,我们来看一下位图法的查询过程。

如果要查找 posting list A 和 B 的公共元素,我们可以将 A、B 两个位图中对应的位置直接做 and 位运算(复习一下 and 位运算:0 and 0 = 0; 0 and 1 = 0; 1 and 1 = 1)。由于位图的长度是固定的,因此两个位图的合并运算时间代价也是固定的。并且由于 CPU 执行位运算的效率非常快,因此,在位图总长度不是特别长的情况下,位图法的检索效率还是非常高的。

相关文章
|
11月前
|
监控 Java 开发工具
Android 崩溃监控实战:一次完整的生产环境崩溃排查全流程
某 App 新版上线后收到大量用户投诉 App 闪退和崩溃。仅凭一条崩溃日志和会话追踪,团队如何在2小时内锁定「快速刷新导致数据竞态」这一根因?本文带你复现真实生产环境下的完整排查路径:从告警触发、堆栈分析、符号化解析,到用户行为还原——见证 RUM 如何让“无法复现的线上崩溃”无所遁形。
1382 99
|
11月前
|
消息中间件 人工智能 NoSQL
AgentScope x RocketMQ:打造企业级高可靠 A2A 智能体通信基座
Apache RocketMQ 推出轻量级通信模型 LiteTopic,专为 AI 场景设计,结合 A2A 协议与 AgentScope 框架,实现多智能体高效、可靠协作,支持海量会话持久化、断点续传与动态订阅,重塑企业级 AI 应用架构。
542 28
|
11月前
|
人工智能 网络协议 Java
一文带你玩转 WebSocket 全链路可观测
在 AI 实时交互爆发的时代,WebSocket 成为核心协议。但其双向、长连接、流式传输特性,让传统链路追踪频频失效。阿里云 LoongSuite 基于 OpenTelemetry 标准,结合探针增强与自定义扩展,首次实现 WebSocket 全链路可观测,支持 Span 粒度控制、上下文透传、异步衔接与关键性能指标采集。
1111 97
|
12月前
|
缓存 运维 监控
一次内存诊断,让资源利用率提升 40%:揭秘隐式内存治理
阿里云云监控 2.0 推出 SysOM 底层操作系统诊断能力,基于 eBPF + BTF 协同分析,无需侵入业务,即可一键完成从物理页到文件路径、再到容器进程的全栈内存归因,让“黑盒内存”无所遁形。
1724 137
|
11月前
|
SQL 人工智能 自然语言处理
让AI真正懂数据:猫超Matra项目中的AI知识库建设之路
本文介绍猫超基于大模型的AI数据助手Matra实践,构建面向Data Agent的知识库体系,通过知识图谱与ReAct框架实现智能取数,提升数据研发效率与业务分析能力。
1216 27
让AI真正懂数据:猫超Matra项目中的AI知识库建设之路
|
8月前
|
存储 自然语言处理 算法
Elasticsearch 核心命脉:倒排索引、分片机制与全链路高性能调优实战
本文深度解析Elasticsearch三大核心:倒排索引(Term Dict/Posting List/FST压缩)、分片机制(主/副本协同、路由算法)及全链路调优(写入/查询/分片/JVM),辅以ES 8.x实战代码,助开发者突破性能瓶颈,构建高可用、高性能搜索系统。
1075 1
|
9月前
|
人工智能 自然语言处理 运维
保姆级教程:2026年OpenClaw(Clawdbot)本地安装与阿里云部署+WhatsApp集成步骤指南
2026年,OpenClaw(原Clawdbot)已成为轻量化、高可用、全平台兼容的开源AI智能体框架,支持本地私有化部署与阿里云云端7×24小时稳定运行,可无缝对接WhatsApp实现全球范围AI交互。本文从零开始,提供本地全平台部署、2026阿里云极简部署、WhatsApp通道集成的完整流程,附带可直接执行的代码命令、权限配置、端口放行、服务自启与问题排查方案,全程无无关平台信息,新手也能一次性跑通。
1540 3
|
7月前
|
人工智能 自然语言处理 数据可视化
阿里云JVS Claw是干什么的,有哪些特点和优势?
JVS Claw(“龙虾”)是基于OpenClaw深度定制的云端AI智能体平台,2026年3月上线。开箱即用、手机可控,提供独立ClawSpace(6核CPU/12GB内存),支持自然语言驱动任务、可视化执行、自进化技能及云+本地双模式。新用户享7天免费试用。(239字)
阿里云JVS Claw是干什么的,有哪些特点和优势?