C0726N02-2-索引模块技术文档

索引模块是向量数据库的核心组件，负责向量数据的存储、索引构建和高效检索。该模块采用LSM-Tree架构，结合图索引算法，实现了高性能的向量相似性搜索。

2. 核心数据结构

2.1 Collection（集合）

集合是数据组织的最高层抽象，定义为四元组：

$\mathcal{C} = (\mathcal{S}, \mathcal{M}, \mathcal{I}, \mathcal{F})$

其中：

• $\mathcal{S}$: 段集合 $\{S_1, S_2, ..., S_n\}$
• $\mathcal{M}$: 元数据管理器
• $\mathcal{I}$: ID映射表
• $\mathcal{F}$: 前向索引

2.1.1 生命周期管理

集合状态转换图：

INITIALIZED → SERVING → DROPPED
     ↓           ↓
   ERROR ←─── SUSPENDED

状态转换函数：

$\sigma: \mathcal{C} \times \mathcal{E} \rightarrow \mathcal{C}'$

其中 $\mathcal{E}$ 为事件集合，$\mathcal{C}'$ 为新状态。

2.1.2 LSM-Tree结构

集合采用多层LSM-Tree结构：

Level 0: Memory Segments (C₀)
├── Writing Segment
└── Dumping Segment

Level 1: Persist Segments (C₁)
├── Segment₁
├── Segment₂
└── ...

Level i: Compacted Segments (Cᵢ)

层级容量约束：

$|C_i| \leq \alpha^i \cdot |C_0|$

其中 $\alpha > 1$ 为扩展因子。

2.2 Segment（段）

段是数据存储和索引的基本单元，定义为：

$S = (\mathcal{D}, \mathcal{G}, \mathcal{T}, \mathcal{R})$

其中：

• $\mathcal{D}$: 文档集合 $\{d_1, d_2, ..., d_m\}$
• $\mathcal{G}$: 图索引结构
• $\mathcal{T}$: 段元数据
• $\mathcal{R}$: 读取器集合

2.2.1 段状态机

CREATED → WRITING → DUMPING → PERSIST
    ↓        ↓         ↓         ↓
  ERROR ←── ERROR ←── ERROR ←── COMPACTING

2.2.2 文档标识符映射

每个段维护文档ID到主键的双向映射：

$\phi: \text{DocID} \rightarrow \text{PrimaryKey}$

$\phi^{-1}: \text{PrimaryKey} \rightarrow \text{DocID}$

其中 $\text{DocID} \in [\text{min\_doc\_id}, \text{max\_doc\_id}]$。

2.3 Column Index（列索引）

列索引负责单个向量列的索引构建和查询，采用图索引算法。

2.3.1 图索引结构

对于向量集合 $\mathcal{V} = \{\mathbf{v}_1, \mathbf{v}_2, ..., \mathbf{v}_n\}$，构建有向图 $G = (V, E)$：

• 顶点集：$V = \{1, 2, ..., n\}$
• 边集：$E \subseteq V \times V$

边的构建规则：

$(i, j) \in E \iff j \in \text{KNN}(\mathbf{v}_i, k_{\text{build}})$

其中 $k_{\text{build}}$ 为构建时的邻居数量。

2.3.2 图搜索算法

基于贪心搜索的近似最近邻算法：

Algorithm: Graph-based ANN Search
Input: query q, graph G, entry points E, search_k
Output: k nearest neighbors

1. Initialize candidate set C = E
2. Initialize result set R = ∅
3. While |C| > 0 and |R| < search_k:
4.   Select closest candidate c from C
5.   Remove c from C
6.   Add c to R
7.   For each neighbor n of c in G:
8.     If n not visited and δ(q, vₙ) < max_dist(R):
9.       Add n to C
10. Return top-k from R

时间复杂度：$O(k_{\text{search}} \cdot d \cdot \log k)$

其中 $k_{\text{search}}$ 为搜索参数，$d$ 为向量维度。

3. 索引构建算法

3.1 增量索引构建

对于新插入的向量 $\mathbf{v}_{\text{new}}$：

1. 邻居发现：计算 $\text{KNN}(\mathbf{v}_{\text{new}}, k_{\text{build}})$
2. 边添加：添加边 $(\text{new}, j)$ 对所有 $j \in \text{KNN}(\mathbf{v}_{\text{new}}, k_{\text{build}})$
3. 反向连接：对每个邻居 $j$，评估是否添加边 $(j, \text{new})$
4. 度数控制：确保每个顶点的出度不超过 $k_{\text{max}}$

3.2 索引优化

3.2.1 图剪枝

移除冗余边以提高搜索效率：

对于顶点 $i$ 的邻居集合 $N(i)$，移除边 $(i, j)$ 当且仅当：

$\exists k \in N(i) \setminus \{j\}: \delta(\mathbf{v}_i, \mathbf{v}_k) + \delta(\mathbf{v}_k, \mathbf{v}_j) \leq (1 + \epsilon) \cdot \delta(\mathbf{v}_i, \mathbf{v}_j)$

其中 $\epsilon$ 为剪枝阈值。

3.2.2 入口点选择

选择图的入口点集合 $\mathcal{E}$ 以最小化平均搜索路径长度：

$\mathcal{E}^* = \arg\min_{\mathcal{E}} \mathbb{E}[\text{PathLength}(\mathbf{q}, \mathcal{E})]$

采用启发式算法：选择度数最高且分布均匀的顶点作为入口点。

4. 内存管理

4.1 段内存布局

Segment Memory Layout:
┌─────────────────┐
│   Segment Meta  │  ← 段元数据
├─────────────────┤
│   ID Mapping    │  ← 文档ID映射
├─────────────────┤
│   Delete Store  │  ← 删除标记
├─────────────────┤
│   Column Data   │  ← 列数据
│   ┌───────────┐ │
│   │  Vectors  │ │  ← 向量数据
│   ├───────────┤ │
│   │   Graph   │ │  ← 图索引
│   └───────────┘ │
└─────────────────┘

4.2 内存池管理

采用分层内存池策略：

• 小对象池：管理 < 1KB 的小对象
• 中对象池：管理 1KB - 1MB 的中等对象
• 大对象池：管理 > 1MB 的大对象

内存分配函数：

$\text{Allocate}(\text{size}) = \begin{cases} \text{SmallPool.alloc}(\text{size}) & \text{if size} < 1\text{KB} \\ \text{MediumPool.alloc}(\text{size}) & \text{if } 1\text{KB} \leq \text{size} < 1\text{MB} \\ \text{LargePool.alloc}(\text{size}) & \text{if size} \geq 1\text{MB} \end{cases}$

5. 并发控制

5.1 读写分离

采用MVCC（多版本并发控制）机制：

• 写操作：在新版本上进行，不影响正在进行的读操作
• 读操作：基于快照隔离，读取一致性视图
• 版本管理：通过LSN（Log Sequence Number）进行版本控制

5.2 锁机制

采用细粒度锁策略：

• 集合级锁：保护集合元数据
• 段级锁：保护段状态转换
• 列级锁：保护列索引更新

锁获取顺序：Collection → Segment → Column，避免死锁。

6. 性能优化

6.1 缓存策略

多级缓存架构：

L1 Cache: Hot Vectors (LRU)
    ↓
L2 Cache: Graph Neighbors (LFU)
    ↓
L3 Cache: Segment Metadata (FIFO)
    ↓
Disk Storage

6.2 预取机制

基于访问模式的智能预取：

$\text{Prefetch}(\mathbf{q}) = \bigcup_{i \in \text{KNN}(\mathbf{q}, k_{\text{prefetch}})} \text{Neighbors}(i)$

6.3 向量量化

支持多种量化技术：

• 标量量化：$Q(x) = \text{round}(\frac{x - \mu}{\sigma} \cdot 2^{b-1})$
• 乘积量化：将向量分割为子向量，分别量化
• 残差量化：基于残差的层次量化

7. 错误处理与恢复

7.1 故障检测

• 内存错误：通过校验和检测
• 磁盘错误：通过CRC校验
• 网络错误：通过超时和重试机制

7.2 恢复机制

• 段级恢复：重建损坏的段
• 索引重建：从原始数据重建索引
• 增量恢复：基于WAL的增量恢复

8. 性能指标

8.1 查询性能

• 查询延迟：P99 < 10ms
• 查询吞吐量：> 10K QPS
• 召回率：> 95% @ top-100

8.2 索引性能

• 构建速度：> 100K vectors/sec
• 内存使用：< 2x 原始数据大小
• 磁盘使用：< 1.5x 原始数据大小