2. 倒排索引基础：定义、对比与核心数据结构
倒排索引（Inverted Index）是全文检索与搜索引擎的基石。在 Kubernetes 集群中，无论是日志聚合（如 Elasticsearch）、事件搜索还是配置审计，底层都依赖倒排索引实现毫秒级的关键词定位。本节从定义出发，通过与正排索引的对比，深入剖析词典、倒排表、跳表三大核心数据结构。
2.1 倒排索引定义
倒排索引是一种以“词项”为键、以“包含该词项的文档 ID 列表”为值的索引结构。它从文档集合中提取所有不重复的词项（Term），并为每个词项记录出现该词项的文档编号及位置信息。
核心思想： 将“文档 → 词项”的正向映射，转换为“词项 → 文档列表”的逆向映射，从而在查询时直接通过词项定位文档，无需遍历所有文档。
一个典型的倒排索引条目结构如下：
词项（Term） → [ (文档ID, 词频, [位置列表]), ... ]
示例：
"Kubernetes" → [ (doc1, 3, [12, 45, 78]), (doc3, 1, [23]) ]
"Pod" → [ (doc1, 2, [5, 90]), (doc2, 4, [10, 34, 56, 101]) ]2.2 正排索引 vs 倒排索引
正排索引（Forward Index）以文档 ID 为键，存储文档包含的词项列表；倒排索引则相反。两者在存储、查询场景上存在本质差异。
| 对比维度 | 正排索引 | 倒排索引 |
|---|---|---|
| 映射方向 | 文档 ID → 词项列表 | 词项 → 文档 ID 列表 |
| 典型查询 | “给定文档，包含哪些词？” | “给定词项，出现在哪些文档？” |
| 查询效率 | 遍历文档内容，O(N) 扫描 | 直接定位词项，O(1) 或 O(log N) |
| 存储冗余 | 低，仅存储原始文档 | 较高，需额外存储词典+倒排表 |
| 适用场景 | 文档归档、全文备份 | 搜索引擎、日志检索、实时查询 |
| K8s 场景 | etcd 原始事件存储 | kube-apiserver 审计日志搜索 |
实践要点： 在 Kubernetes 集群中，正排索引用于持久化存储（如 etcd 快照），而倒排索引用于查询加速（如 Elasticsearch 对 Pod 日志的全文检索）。两者通常配合使用，正排保证数据完整性，倒排保证查询性能。
2.3 核心数据结构
倒排索引由三大核心组件构成：词典（Dictionary）、倒排表（Posting List）、跳表（Skip List）。下图展示了三者在一次查询中的协作流程。
2.3.1 词典（Dictionary）
词典是倒排索引的入口，存储所有不重复的词项及其指向倒排表的指针。常见的词典实现方式包括：
- 哈希表： O(1) 查找，适合精确匹配，但不支持范围查询和前缀搜索。
- B+ 树： O(log N) 查找，支持范围扫描和前缀匹配，是数据库和搜索引擎的常用选择。
- 跳跃表： O(log N) 查找，实现简单，支持并发操作，在 Redis 和 Lucene 中均有应用。
K8s 场景注意： 在 Kubernetes 集群中，词典的规模取决于日志/事件的词项数量。一个中等规模集群（1000+ Pod）每天可能产生数亿条日志，词典可能包含数百万个词项。此时应优先选择 B+ 树或跳跃表，避免哈希表的内存膨胀和范围查询缺陷。
2.3.2 倒排表（Posting List）
倒排表是每个词项对应的文档 ID 有序列表，通常还包含词频（Term Frequency）和位置信息。为了提高存储效率，倒排表采用多种压缩技术：
| 压缩技术 | 原理 | 压缩比 | 适用场景 |
|---|---|---|---|
| Frame of Reference (FOR) | 将文档ID分组，每组减去最小值后用小整数存储 | 3x – 10x | 密集文档ID序列 |
| Delta Encoding | 存储相邻文档ID的差值 | 2x – 5x | 通用场景 |
| Variable Byte Encoding | 用变长字节表示整数，小值用更少字节 | 2x – 4x | 混合分布 |
| Simple9 / Simple16 | 将多个小整数打包到一个32位字中 | 4x – 8x | 高性能场景 |
2.3.3 跳表（Skip List）
跳表是一种基于有序链表的多层索引结构，用于加速倒排表的合并与查找操作。在搜索引擎中，多个词项的倒排表需要做交集（AND）、并集（OR）运算，跳表通过“跳跃”跳过不匹配的文档ID，大幅减少比较次数。
跳表的核心操作流程：
- 构建： 在有序链表基础上，随机选取部分节点作为上层索引，形成多层结构。
- 查找： 从最高层开始，向右移动直到目标值或下一节点大于目标值，然后下降一层继续。
- 合并： 对两个跳表进行 AND 操作时，同时遍历两个跳表，利用跳跃特性跳过不可能匹配的区间。
性能对比： 在倒排表合并场景中，使用跳表比线性扫描快 10–100 倍。例如，两个各包含 100 万文档ID的倒排表做交集，线性扫描需要 100 万次比较，而跳表仅需约 2 万次比较（取决于跳跃步长）。
下面通过一个具体的跳表合并示例，展示其加速原理：
2.4 本章小结
- 倒排索引 以词项为键、文档ID列表为值，实现从关键词到文档的快速定位。
- 正排索引 与倒排索引互为补充，正排用于存储，倒排用于查询。
- 词典 是倒排索引的入口，哈希表、B+树、跳跃表各有优劣，K8s 场景推荐 B+树或跳跃表。
- 倒排表 存储有序文档ID列表，通过 FOR、Delta Encoding 等压缩技术降低存储开销。
- 跳表 通过多层索引加速倒排表的合并与查找，在 AND/OR 查询中性能提升显著。