Lance 向量索引设计

LAYER 1 · CLUSTERING

聚类层

缩小搜索范围 · 全局 k-means

IVF

LAYER 2 · SUB-INDEX

子索引层

分区内搜索结构

FLAT HNSW

LAYER 3 · QUANTIZATION

量化层

压缩存储 · 加速距离计算

FLAT PQ SQ RQ

IDX

index.idx

搜索图结构 + IVF 元数据

字段	类型	说明
Arrow Schema — HNSW 子索引
__vector_id	uint64	节点 ID
__neighbors	list<u32>	邻居节点（多层）
_distance	list<f32>	到邻居的距离
Arrow Schema Metadata
lance:index	JSON	type, distance_type
lance:ivf	"1"	Global Buffer 引用
Global Buffer — Protobuf
IVF.centroids_tensor	Tensor	[num_part, dim] 质心
IVF.offsets	uint64[]	各分区起始行号
IVF.lengths	uint32[]	各分区向量数量

AUX

auxiliary.idx

量化后向量存储（按 partition 顺序）

量化方式	列结构	压缩
FLAT	_rowid + flat[dim]	1× 无损
PQ	_rowid + __pq_code[m]	8–32× 高压缩
SQ	_rowid + __sq_code[dim]	4× 中压缩
RQ	_rowid + _rabit_codes[dim/8] + add_factors + scale_factors	32× 极致
Global Buffer
PQ 码本	Tensor [256, m, d/m]	float32
RQ 旋转矩阵	Tensor [dim, dim]	正交矩阵

物理层 · Fragments（按写入批次）

Fragment-0

row 0–999

Fragment-1

row 1000–1999

Fragment-2

row 2000–2999

Fragment-3 ✦ new

未索引

→

k-means
全局聚类
centroids

索引层 · IVF Partitions（按语义相似度）

Partition-0 · 质心 C₀

rowid: 0, 5, 1002, 2001 …（跨 Fragment）

Partition-1 · 质心 C₁

rowid: 1, 1001, 1003, 2003 …（跨 Fragment）

Partition-2 · 质心 C₂

rowid: 3, 1004, 2000, 2002 …（跨 Fragment）

⚠

auxiliary.idx 中向量按 Partition 顺序排列，而非 Fragment 顺序。每条记录保留 _rowid 回溯原始数据，Fragment 物理位置信息被完全"打散"。

STEP 1

查询向量

q ∈ ℝᵈ
nprobes 参数

→

STEP 2

IVF 粗筛

与 centroids_tensor
计算距离，取最近
nprobes 个分区

→

STEP 3

分区内搜索

FLAT: 线性扫描
HNSW: 图遍历
加载 auxiliary.idx

→

STEP 4

量化距离计算

PQ: 距离表查找
SQ/RQ: 近似计算
+ refine_factor

→

STEP 5

结果合并

indexed 结果
+ unindexed
暴力搜索 fallback

写路径：append + optimize

append() — 写新 Fragment
顺序写，极快；原有索引文件不动

搜索立即可用：新 Fragment 走 brute-force fallback

optimize_indices() — 触发 Delta Index
① 用已有 centroids 分配新向量到最近分区
② 按分区顺序写出 delta auxiliary.idx
③ 更新 offsets / lengths 元数据
④ 发布新 Manifest 版本

不需要重跑 k-means —— centroids 复用

数据分布漂移过大时触发 full retrain

Delta 文件积累与 Compaction

初始建索引 auxiliary.idx（全量）

optimize ×1 auxiliary.idx delta_1

optimize ×2 auxiliary.idx delta_1 delta_2

含未索引 auxiliary.idx delta_1 brute

compaction auxiliary.idx（合并后）

◈

搜索时需同时查询所有 delta 文件，delta 积累过多时 Cloud/Enterprise 后台自动执行类 LSM Compaction，合并回单一 auxiliary.idx。

索引类型	搜索速度	召回率	内存占用	适用场景
IVF_FLAT	中	最高	大	精度优先，中小数据集
IVF_PQ	很快	中	小	大规模，内存受限
IVF_SQ	快	较高	中	均衡型首选
IVF_HNSW_SQ	极快	高	中	在线服务，低延迟
IVF_RQ	快	中	极小	超大规模，极低内存