4. 倒排索引与密文索引结构

在云端密文检索平台中，倒排索引是决定检索效率的核心数据结构。如果把密文文档集合比作一座图书馆，倒排索引就是那张“关键词 → 文档编号”的索引卡片柜：给定一个词，系统无需扫描全部文档，就能直接定位包含该词的文档集合。本节先讲清明文倒排索引的基本原理，再说明在密文场景下如何把它改造成可安全存储、可高效检索的加密倒排索引，并给出可落地的存储布局。

一、明文倒排索引的基本原理

倒排索引（Inverted Index）由“词典”和“倒排列表”两部分组成。词典（Dictionary）保存所有出现过的关键词，倒排列表（Posting List）保存每个关键词对应的文档集合及其附加信息。与之相对的正排索引是“文档 → 关键词”，适合按文档读取；倒排索引是“关键词 → 文档”，适合按关键词检索，这正是搜索场景的主流选择。

一个典型的倒排列表项通常包含：文档编号 docID、词频 tf（该词在文档中出现次数）、位置列表 positions（词在文档中的偏移，用于短语检索和高亮）。例如有三篇文档：D1=“云端 密文 检索 平台”，D2=“密文 检索 效率”，D3=“云端 检索 平台”。分词并去停用词后，可得到如下倒排结构（示例数据，仅用于说明）：

词典          倒排列表（docID:tf:positions）
云端     →   D1:1:[0]   D3:1:[0]
密文     →   D1:1:[1]   D2:1:[0]
检索     →   D1:1:[2]   D2:1:[1]   D3:1:[1]
平台     →   D1:1:[3]   D3:1:[2]
效率     →   D2:1:[2]

检索“密文 检索”时，系统分别取出两个倒排列表，做交集运算，得到同时包含两词的文档集合 {D1, D2}，再按词频或相关度排序返回。可以看到，倒排索引把“全表扫描”变成了“按词取表 + 集合运算”，这是它高效的根本原因。

构建倒排索引的典型流程是：文档采集 → 分词与归一化（转小写、去停用词、词干化）→ 生成 (词, docID, 位置) 三元组 → 按词聚合排序 → 写入词典与倒排列表。工程上还会对 docID 做差值编码（delta encoding）、对倒排列表做分块压缩（如 Variable Byte、PForDelta），以降低存储和 I/O 开销。

二、密文倒排索引的构建方法

直接把明文倒排索引上传到云端是不可接受的：词典和倒排列表会泄露关键词、文档数量、词频分布等敏感信息。密文倒排索引的目标是：云端只能看到加密后的索引项和检索令牌，无法还原关键词与文档的对应关系，但仍能完成匹配运算。

主流做法是“关键词加密 + 倒排列表加密”的双层结构。第一步，对每个关键词 w 计算确定性陷门（trapdoor）：T(w) = H(K₁, w)，其中 H 是抗碰撞哈希，K₁ 是仅客户端持有的密钥。相同关键词得到相同陷门，因此云端可以按陷门聚合，但无法从陷门反推 w。第二步，对倒排列表内容用对称加密保护：E_K2(docID ‖ tf ‖ positions)，K₂ 同样由客户端持有。云端存储的是 (T(w), 加密倒排列表) 这样的键值对。

检索时，客户端本地计算查询词的陷门 T(w)，把它作为检索令牌发给云端；云端用 T(w) 查到对应密文倒排列表，返回给客户端；客户端用 K₂ 解密，得到 docID 集合，再在本地做交集、排序。整个过程中，云端只见到陷门和密文，不知道查询的是什么词，也不知道命中了哪些文档。

三、存储布局与工程实现

密文倒排索引在存储层通常采用“词典区 + 倒排区”分离的布局。词典区是一个有序的 (陷门, 倒排区偏移, 长度) 表，支持二分查找或 B+ 树定位；倒排区按陷门顺序连续存放加密倒排列表，便于顺序读取和批量解密。下面给出一个可参考的存储结构示例（字段为示例设计，非实测结果）：

增量更新时，新增文档会生成新的倒排项。若直接改写原倒排列表，会暴露“哪些旧词被更新”，因此工程上常采用追加式布局：新倒排项写入倒排区尾部，词典区记录多个分段（segment）的偏移，检索时合并各分段结果。配合前向安全方案，旧陷门无法匹配新写入的索引项，从而降低更新泄露。

下面用一张图概括密文倒排索引从构建到检索的完整数据流与存储布局关系：

从图中可以看到，密文倒排索引的关键设计点有三个：一是用陷门替代明文关键词作为词典键，保证云端无法识别词义；二是用对称加密保护倒排列表内容，保证 docID、词频、位置不外泄；三是采用追加式分段存储，配合前向安全机制，降低增量更新带来的关联泄露。实际部署时，还需根据文档规模选择压缩算法、分片策略和缓存策略，在检索延迟与隐私强度之间取得平衡。

小结：明文倒排索引用“关键词 → 文档”的映射换取检索效率；密文倒排索引在此基础上，用确定性陷门实现可定位、用对称加密实现内容保密、用追加分段实现安全更新。理解这三层结构，是后续实现密文检索、排序与更新的基础。