索引和查询处理

索引和查询处理包括数据结构和算法，这些数据结构和算法使搜索系统能够通过倒排索引快速回答大型文本集合上的查询。

Definition

索引是数据结构的构建，主要是将术语映射到包含它们的文档的倒排索引，以支持高效查找；而查询处理是遍历这些结构以计算匹配或最适合查询的文档的一组算法。

Scope

该领域涵盖了如何将文本集合转换为可搜索的结构以及如何对其进行查询评估：构建倒排索引、其背后的分词和术语词汇决策、压缩倒排列表以节省空间和加速访问、高效处理查询（包括排序检索和提前终止），以及容错检索技术，如通配符、拼写校正和语音匹配。它涉及快速检索的系统工程，这与定义排序的检索模型和衡量质量的评估方法不同。

Sub-topics

• 索引压缩
• 倒排索引
• 查询处理与优化
• 容错和通配符检索

Core questions

• 如何为大型、不断变化的集合构建和更新倒排索引？
• 如何在不减慢查询评估速度的情况下压缩倒排列表？
• 如何高效评估查询，特别是对数百万文档的排序查询？
• 系统如何在不为每个文档评分的情况下检索到好的结果？
• 系统如何处理拼写错误、通配符和近似匹配？

Key concepts

• 倒排索引
• 倒排列表
• 分词和术语词汇
• 索引构建（BSBI, SPIMI）
• 索引压缩
• 逐文档和逐词评估
• 动态剪枝和提前终止
• 容错检索

Key theories

倒排索引作为核心数据结构

将每个术语映射到包含该术语的文档（和位置）的倒排列表，使得检索只触及包含查询术语的文档，从而使其成为可伸缩文本搜索的基础结构。

压缩-效率权衡

使用紧凑的整数编码对文档ID间隔和术语频率进行编码，可以显著缩小索引，并且通过减少输入/输出和改善缓存行为，还可以加速查询处理。

高效的排序查询评估

逐文档和逐词策略，结合动态剪枝和提前终止技术，允许系统返回排名靠前的结果，而无需对整个集合进行完整评分。

Clinical relevance

倒排索引和高效的查询处理是每个生产搜索系统的核心引擎，从网络搜索引擎和开源搜索平台到企业和数据库全文搜索。它们的效率直接决定了查询延迟、硬件成本以及可交互搜索的集合规模。

History

倒排文件自最早的信息系统以来就已用于文本搜索，但索引构建、压缩和高效评估的现代理论在1990年代得到巩固，特别是Witten、Moffat和Bell的《Managing Gigabytes》一书。Zobel和Moffat在2006年的调查总结了二十年来倒排索引的研究，当时网络规模的搜索使得效率至关重要。

Key figures

• Justin Zobel
• Alistair Moffat
• Ian H. Witten
• W. Bruce Croft

Seminal works

• zobel2006
• wittenmgb1999
• manning2008

Frequently asked questions

为什么倒排索引优于扫描文档？

对于大规模数据，每次查询都扫描所有文档太慢了。倒排索引允许系统直接跳转到包含查询术语的一小部分文档，因此查询时间取决于所涉及的倒排列表，而不是整个集合的大小。

压缩索引会减慢搜索速度吗？

通常恰恰相反。更小的索引减少了磁盘和内存流量，并且现代整数编码解压缩速度非常快，因此在输入/输出上节省的时间和改进的缓存行为通常会超过解码成本，使得压缩索引既更小又更快。