# 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聚类与精确向量存储，在簇内进行精确搜索    |
   
#### 系统索引
系统索引是支持内部表维护和行标识符解析的辅助结构，不由最终用户直接查询。例如Fragment Reuse Index支持压缩后的高效重映射。
- 碎片重用索引 (Fragment Reuse Index, FRI)用于在压缩 (compaction) 和数据集更新期间优化碎片操作。
- MemWAL索引作为所有MemWAL元数据的集中式结构。它存储配置（分片规格、需维护的索引）、合并进度以及分片状态快照。