第四章 索引结构基础：倒排索引与B树

说到密文索引，很多人第一反应是「把B树搬过来，加密一下不就行了？」。嗯，我曾经也这么想，直到在项目中踩了坑才发现——倒排索引和B树，这两兄弟虽然都叫索引，但底层的数据组织方式完全是两套思路。今天咱们就掰开揉碎了聊聊。

4.1 B树：数据库的定海神针

B树是什么？说白了就是一种平衡的多路搜索树。它有个核心特性：每个节点可以存储多个键值对，并且保持有序。叶子节点在同一层，查询任何记录走的路径长度都差不多。

我个人习惯把B树想象成一个分层索引目录。根节点放几把「钥匙」，告诉你下一层去哪找；中间节点继续分叉；最后到叶子节点，数据就在那儿等着你。

B树的关键参数

参数	含义	典型值
阶数 (m)	每个节点最多能有多少个子节点	100~500（取决于页面大小）
高度 (h)	从根到叶子需要经过多少层	对于百万级数据，h ≤ 3
节点利用率	节点中实际存储的键数与最大容量之比	约 50%~70%

你想想看，一个三层的B树就能处理几百万条记录。为什么？因为每个节点可以装几百个键，分叉极多。我曾经用B树给一个明文数据库做索引，两千万条记录，树高才4层——每次查询最多读4个页面，速度飞快。

4.2 倒排索引：全文检索的灵魂

倒排索引就完全是另一回事了。它不关心键的顺序，它关心的是「某个词出现在哪些文档里」。

结构很简单：一个词典（Dictionary），每个词后面挂一个倒排列表（Posting List）。列表里存的是文档ID列表，可能还有位置、频率等信息。

举个例子：

文档1: "猫 喜欢 鱼"
文档2: "狗 喜欢 骨头"
文档3: "猫 讨厌 洗澡"

倒排索引：
"猫"   -> [1, 3]
"喜欢" -> [1, 2]
"鱼"   -> [1]
"狗"   -> [2]
"骨头" -> [2]
"讨厌" -> [3]
"洗澡" -> [3]

查询「猫 AND 鱼」怎么做？取出"猫"的列表 [1,3]，取出"鱼"的列表 [1]，求交集 → [1]。这就是倒排索引最擅长的——集合运算。

4.3 密文索引面临的核心矛盾

把这两种结构搬到密文场景下，麻烦就来了。

B树依赖键的有序性才能做范围查询、快速定位。一旦加密，顺序被彻底打乱——除非你使用保序加密（OPE），但OPE有泄漏风险，我在项目中吃过亏。

倒排索引依赖词典的精确匹配和倒排列表的交集运算。密文状态下，你不能直接比较两个密文是否相等，也不能直接做位图交集——都需要可搜索加密（SSE）的辅助。

为什么不能简单地把B树的节点加密了事？因为密文不可比较。你拿着一个加密后的键，想去B树里查找，找不到，因为密文没有顺序可言。除非你额外维护一个比较用的辅助结构——这就引入了性能代价。

4.4 两种索引在密文场景下的适用性对比

维度	B树	倒排索引
查询类型	精确、范围、前缀	关键词匹配、布尔查询
密文友好度	低（需要OPE或辅助结构）	中等（依赖SSE和位图）
数据更新	容易（原地更新）	困难（倒排列表重写代价高）
空间开销	低（约数据量的1.2~1.5倍）	高（倒排列表可能膨胀数倍）
典型适用	结构化记录检索	全文搜索、日志分析

这张表你看明白了吧？没有银弹。密文场景下，你需要根据业务查询类型决定用哪种结构，或者把两者结合起来。

4.5 核心知识点体系

为了让结构更直观，我画了一张框架图。它把本章的知识点串起来了——先认识两种索引，再理解它们在明文下的工作机制，最后分析密文移植的挑战和应对思路。

4.6 我的一些实践建议

如果你刚接触密文索引，我建议按这个顺序理解：

1. 先吃透明文B树和倒排索引的底层实现。 不理解明文数据的组织方式，密文优化就是空中楼阁。
2. 然后想清楚你的业务查询类型。 如果是「某个字段在什么范围内」，走B树路线；如果是「包含某些关键词」，走倒排路线。
3. 密文改造时，不要试图完美复制明文结构。 我曾经尝试把B树每个节点独立加密，结果维护比较序的辅助结构比索引本身还大——得不偿失。
4. 多考虑混合策略。 比如用B树处理主键范围查询，用倒排索引处理多字段的布尔组合。

OK，这一章的核心就这些。倒排和B树，一个面向集合运算，一个面向有序搜索。到了密文世界，它们各自的弱点会暴露出来。但反过来想——正是因为不能直接拿来用，才需要我们去做优化，不是吗？