向量索引的增量更新难题：删除与修改如何不破坏索引结构

一句话总结：向量数据库不是"写入一次、查询无限次"的静态系统。当业务要求索引在持续写入、删除、修改中保持可用且性能不劣化时，HNSW 的软删除堆积、IVF 的聚类漂移、增量合并的时延 trade-off，都是你必须面对的工程挑战。

一、为什么增量更新是个真问题

在大多数向量检索的入门教程里，流程是这样的：

1. 准备好一批向量
2. 调用 build_index()
3. 开始 search()

这掩盖了真实业务中的一个核心事实：向量是活的。

推荐系统里，用户画像向量随行为实时变化；RAG 场景下，文档库持续增删改；电商搜索中，商品向量的属性标签每天都在刷新。一个生产环境的向量索引，生命周期可能是数月甚至数年，期间要经历数百万次插入、删除和覆盖写入。

而绝大多数高性能近似最近邻（ANN）索引——HNSW、IVF、PQ、NSG——在设计之初优化的目标是静态数据集上的查询延迟和召回率，而非动态更新下的结构稳定性。这就导致了一个尴尬的工程现实：

构建索引很快，维护索引很难。

二、HNSW：软删除的"幽灵节点"困境

HNSW（Hierarchical Navigable Small World）是目前工业界使用最广泛的图索引。它的核心思想是通过概率跳表结构构建多层导航图，查询时从顶层 coarse graph 逐层向下逼近目标。

2.1 为什么不能直接删节点？

HNSW 的图结构是有向且高度互联的。每个新节点在插入时会通过 efConstruction 次最近邻搜索找到连接点，并向这些邻居建立出边。如果直接物理删除一个节点：

• 出边断裂：被删节点的所有出边消失，它指向的子图可能变得不可达。
• 入边悬空：其他节点指向被删节点的入边变成"死链接"，导致搜索路径中断。
• 连通性破坏：极端情况下，图的连通分量可能分裂，部分区域彻底丢失。

因此，物理删除在 HNSW 中几乎是不可行的——除非你愿意在每次删除后触发局部甚至全局重建。

2.2 软删除：简单但有毒

最常见的 workaround 是软删除（soft delete / logical delete）：

# 伪代码示意
class HNSWNode:
    vector: np.ndarray
    neighbors: List[int]
    deleted: bool = False  # 标记位

def search(query, k):
    candidates = beam_search(query, ef)
    return [n for n in candidates if not n.deleted][:k]

实现简单，查询时跳过标记节点即可。但问题在于：

幽灵节点（Ghost Nodes）会永久污染图结构。

• 被标记删除的节点仍然参与图导航，占用内存，增加搜索时的候选集规模。
• 随着时间推移，删除比例上升（比如达到 30%），有效节点被大量无效节点包围，搜索路径被迫绕行，延迟上升、召回下降。
• 更糟糕的是，新节点插入时仍可能把已删除节点选为邻居，导致"僵尸连接"一代代传递。

2.3 重建：正确但昂贵

当软删除比例超过阈值（通常 10%-20%），系统需要触发重建（rebuild）：

• 全量重建：导出有效向量，重新调用 build_index()。最简单，但期间服务不可用或需要双缓冲（双倍内存）。
• 局部重建：只重建受删除影响的部分子图。理论上更轻量，但实现复杂，需要维护反向索引（谁指向了我），且局部重建后图的全局最优性无法保证。

工程实践中的折中：

给开发者的建议：如果你的 HNSW 索引删除操作占比超过 5%，请尽早设计重建策略，不要等幽灵节点拖垮性能。

三、IVF：聚类漂移与增量合并的两难

IVF（Inverted File Index）是另一种广泛使用的索引结构，尤其在大规模向量检索中（如 Faiss 的 IndexIVFFlat、IndexIVFPQ）。它将向量空间通过 K-Means 聚类划分为 nlist 个桶（voronoi cell），查询时只在最近的 nprobe 个桶内搜索。

3.1 聚类漂移：静态假设的崩溃

IVF 的核心假设是：聚类中心能代表数据分布，且分布是稳定的。

但在增量更新场景下，这个假设迅速失效：

• 新数据分布偏移：初始聚类中心基于历史数据，新流入的向量可能集中在完全不同的区域。如果强行插入到最近的旧桶，会导致桶内数据分布极不均匀，搜索时需要访问更多桶才能覆盖目标区域。
• 桶容量失衡：某些桶持续膨胀（比如热门类目），搜索时扫描该桶的线性成本激增；另一些桶则长期空置，浪费内存。
• 聚类质量不可逆劣化：IVF 的查询效率高度依赖 K-Means 的聚类质量。一旦分布漂移，除非重新训练聚类中心，否则性能只会越来越差。

3.2 为什么不能直接插入新向量？

IVF 的插入操作本身很简单：计算新向量到所有聚类中心的距离，放入最近的桶。但问题在于：

• 没有删除机制：IVF 通常不支持高效删除。如果必须删除，只能在桶内做线性扫描标记，和 HNSW 的软删除类似，代价是查询时扫描到已删除向量再过滤。
• 聚类中心不更新：新向量不断进入，但中心点固定在初始训练结果，导致"结构性偏差"。

3.3 增量合并策略：小索引 + 大索引

工业界常用的 workaround 是增量合并（incremental merge），典型代表是 Faiss 的 OnDiskInvertedLists 和 IndexIVF::merge_from，以及 Milvus 等系统的 segment-based 架构：

┌─────────────────────────────────────┐
│           查询层                     │
│   查询同时检索 Base Index +         │
│   Incremental Index，合并结果        │
└─────────────────────────────────────┘
            ↓
┌──────────────┐    ┌────────────────┐
│  Base Index  │    │ Incremental    │
│  (大，只读)   │    │ Index (小，可写) │
│  IVF 结构    │    │  可以是 Flat/  │
│  聚类中心固定 │    │  小 HNSW 等    │
└──────────────┘    └────────────────┘
            ↓
      定期合并（Compaction）
   将 Incremental 合并回 Base，
   同时重新训练聚类中心

工作流程：

1. 写入：新向量先进入小型的增量索引（通常用暴力搜索或轻量 HNSW）。
2. 查询：同时查询 Base Index 和 Incremental Index，合并 Top-K 结果。
3. 合并（Compaction）：当增量索引达到一定大小，或触发定时任务时：
   • 导出 Base + Incremental 的全部有效向量
   • 重新运行 K-Means 训练新的聚类中心
   • 构建新的 Base Index
   • 原子切换

Trade-off 分析：

给开发者的建议：IVF 的增量更新没有完美解。如果你的场景写入频繁且查询延迟敏感，考虑用 HNSW 替代 IVF；如果必须用 IVF（比如需要 PQ 压缩），请设计好 Compaction 的调度策略，避免在业务高峰触发合并。

四、版本快照机制：并发更新与查询的隔离

即使解决了索引结构的更新问题，还有一个更底层的挑战：并发控制。

当索引正在重建、合并或修改聚类中心时，如何保证查询不受影响？

4.1 双缓冲（Double Buffering）

最直观的方案：

• 维护两个索引实例：Index_A（服务中）和 Index_B（构建中）。
• 更新操作在 Index_B 上完成。
• 完成后原子切换指针：Index_A ← Index_B，旧 Index_A 进入后台释放。

优点：查询零中断，实现简单。

缺点：

• 内存翻倍（两份索引同时存在）。
• 切换瞬间可能有短暂的请求抖动。
• 如果索引极大（百亿级向量），双缓冲的内存成本不可接受。

4.2 写时复制（COW）与轻量快照

对于不支持双缓冲的系统，可以使用写时复制：

• 索引结构本身支持引用计数或不可变节点。
• 删除标记为逻辑删除，新增节点追加到独立区域。
• 查询获取一个"快照句柄"，基于快照时刻的索引视图进行检索，不受后续更新干扰。

代表实现：Milvus 的 Timestamp Oracle + Segment 不可变设计。每个 segment 一旦写入即为只读，删除通过 delta log 记录，查询时合并 base + delta。segment 之间通过版本时间戳进行可见性控制。

4.3 乐观锁与局部更新

对于必须原地更新的结构（如某些 NSG 实现），可以使用乐观锁：

• 查询线程不加锁，读取节点时验证版本号。
• 更新线程修改节点前增加版本号，修改后再次递增。
• 如果查询线程读到不一致状态（版本号奇偶不匹配），重试或跳过。

这种方式实现复杂，且在高并发写入下重试率可能飙升，一般只在特定场景使用。

五、综合选型建议

六、写在最后

向量索引的增量更新问题，本质上是一个结构不变性（structural invariance）与数据动态性（data dynamism）之间的矛盾。

HNSW 的图结构追求导航效率，导致对节点删除高度敏感；IVF 的聚类结构追求空间划分效率，导致对分布漂移高度敏感。没有一种索引能在静态查询性能和动态更新能力上同时达到最优。

作为开发者，你需要根据业务的数据更新频率、查询延迟要求、可用资源预算，选择合理的组合策略：

• 删除少、查询多 → HNSW 软删除 + 低频率重建
• 写入频繁、查询敏感 → HNSW 双缓冲热重建，或干脆用 Flat + 缓存
• 超大规模、成本敏感 → IVF + 增量合并 + 定时 Compaction
• 金融级高可用 → 版本快照 + Segment 不可变架构

向量数据库的选型表上通常只标注了 QPS 和 Recall@K，但生产环境的真正考验在于：当索引运行了三个月后，删除率达到了 25%，凌晨两点还在持续写入时，你的查询延迟是否还能保持在 P99 的 SLA 之内？

这才是增量更新难题的价值所在。