Lance索引介绍

Lance将索引视为独立的、冗余的数据结构，分层构建在表行标识符之上。这使文件格式免于内置搜索结构，并允许索引格式独立于表布局演进。Lance支持三大类索引：标量索引、向量索引和系统索引。

标量索引

标量索引加速对整数、时间戳和字符串等标量数据类型的查询。Lance支持的标量索引请参考表1。

表1 标量索引类型
索引类型	存储文件	加速查询	说明
Zone Map	zonemap.lance	Equals、Range、IsIn、IsNull	将数据分成固定大小的区域，维护min/max/null_count统计信息，用于谓词下推和扫描裁剪。可能包含误报，需要重新检查。
BTree	page_lookup.lance + page_data.lance	Equals、Range、IsIn、IsNull	两级结构，上层BTree缓存于内存，下层子索引存储排序值和行ID。平衡内存结构和磁盘结构。
Bitmap	bitmap_page_lookup.lance	Equals、Range、IsIn、IsNull	使用位数组表示值的存在或缺失，适用于低基数列，提供极快的查询性能。
Bloom Filter	bloomfilter.lance	Equals、IsIn、IsNull	概率数据结构，允许快速成员测试。空间高效，可能有误报但无误漏。使用Split Block Bloom Filter（SBBF）实现，优化SIMD操作。
Full Text Search	tokens.lance + docs.lance + invert.lance + metadata.lance	contains_tokens、match、phrase、boolean、multi_match、boost	倒排索引，将词项映射到包含它们的文档。支持BM25评分、短语查询和多种分词器。
Label List	bitmap_page_lookup. lance	array_has / array_contains、array_has_all、array_has_any	标签列表索引针对每行包含多个标签或标记的列进行了优化。它们使用底层的位图索引，针对多值列提供高效的基于集合的查询。
N-gram	ngram_postings.lance	contains	N-gram 索引将文本分解为重叠的序列（三元组），以实现高效的子字符串匹配。通过在应用 ASCII 折叠和转为小写后，对文本中所有三元组序列进行索引，从而提供快速的文本搜索功能。
R-Tree	page_data.lance	Intersects、Contains、Within、Touches、Crosses、Overlaps、Covers、CoveredBy、IsNull	基于边界框（Bounding Boxes）构建以组织数据。该索引旨在加速基于矩形的修剪操作

向量索引

向量索引专用于高维嵌入的近似最近邻搜索（ANN）。Lance将每个向量索引分为3个部分：聚类（Clustering）、子索引（Sub-Index）和量化（Quantization）。

聚类：将所有向量划分为不同的不相交簇。Lance目前支持使用倒排文件（IVF）作为主要聚类机制，使用k-means聚类算法将向量分区。
子索引：决定向量如何组织以进行搜索。支持FLAT（精确搜索，无近似）和HNSW（分层可导航小世界图，快速近似搜索）。
量化：决定向量如何存储和压缩。支持Product Quantization（PQ，乘积量化）、Scalar Quantization（SQ，标量量化）、RabitQ（RQ，随机旋转二值量化）和FLAT（不量化，保留原始向量）。

索引类型通常由 {clustering}_{sub_index}_{quantization} 构成。若子索引为 FLAT，则通常省略该项，简记为 {clustering}_{quantization}。

表2 向量索引类型
索引类型	名称	说明
IVF_PQ	倒排文件+乘积量化	结合IVF聚类与PQ压缩，实现高效存储和搜索
IVF_HNSW_SQ	倒排文件+HNSW+标量量化	使用IVF粗聚类和HNSW细粒度搜索，配合标量量化
IVF_SQ	倒排文件+标量量化	结合IVF聚类与标量量化，实现平衡压缩
IVF_RQ	倒排文件+RabitQ	结合IVF聚类与RabitQ，使用二值量化实现极限压缩
IVF_FLAT	倒排文件+无量化	使用IVF聚类与精确向量存储，在簇内进行精确搜索