本文介绍搜索引擎的索引建立，更新，查询和压缩技术。
索引基础
倒排索引是搜索引擎用来快速查找包含某个单词的文档集合的数据结构 倒排索引由单词词典和所有单词对应的倒排列表组成
倒排列表由倒排列表项构成，一般包含：
- 文档ID(一般采取文档编号差值方式编码)
- 单词出现次数
- 单词在文档出现位置的信息
索引建立与更新
倒排索引建立
常见建立倒排索引方法：
- 两遍文档遍历法
- 排序法
- 归并法
动态索引及更新
动态索引的三个关键数据结构：
- 倒排索引：对初始文档集合建立的索引结构
- 临时索引：新文档进入系统建立的索引结构
- 已删除文档列表：已删除的文档ID列表
注意：对于动态索引文档更改可认为是文档先被删除然后向系统内增加一篇新的文档。
对于动态索引需要进行更新，常见索引更新策略：
- 完全重建策略
- 再合并策略
- 原地更新策略
- 混合策略
查询处理
基本处理机制
常见查询处理机制有如下两种：
- 一次一文档方式(Doc At a Time)
- 一次一单词方式(Term At a Time)
注意：
- 一次一文档方式实际查询时不必保留所有文档得分，保留得分Top K的文档队列即可。
- 一次一单词方式适用于多词查询，找到包含所有查询词的文档等价于求查询词对应的倒排列表的交集。
多字段和短语查询
实现多字段索引方式：
- 多索引方式
- 倒排列表方式
- 扩展列表方式
常见的支持短语查询技术的方法包括：
- 位置信息索引
- 双词索引
- 短语索引
可混合使用，查询索引优先级：短语索引 > 双词索引 > 常规索引
分布式索引
常见的分布式索引方案：
- 按文档对索引划分
- 按单词对索引划分
其中按文档对索引划分在以下方面有优势：
- 可扩展性
- 负载均衡
- 容错性
- 对查询方式的支持
索引压缩
索引压缩包括对词典的压缩和对倒排列表的压缩。
倒排列表压缩
倒排列表压缩：
- 无损压缩：更常用
- 有损压缩：特殊场合使用
倒排列表压缩算法的基本构件：
- 一元编码
- 二元编码
常用压缩算法：
- Elias Gamma算法
- Elias Delta算法
- Golomb算法
- Rice算法
- 变长字节算法
- SimpleX系列算法
- PForDelta算法
实际使用一般混合采用多种算法。
重排序与裁剪
文档ID重排序通过文档聚类并重排文档ID编号来获得较高的索引压缩率 静态索引裁剪是一种有损压缩算法，通过抛弃一部分不重要的索引项来获得较好的压缩效果。