本页介绍两种用于管理Faiss倒排列表存储的底层C++接口。 这对于将倒排列表存储在键值数据库等外部系统中特别有用。

InvertedLists 抽象类定义了搜索代码（search code）如何访问倒排列表。 只要对象实现了这个接口，就可以用来存储倒排列表。

InvertedListsScanner 进一步细化了访问方式，可以直接对用户自定义的id表和code表执行扫描操作。

IndexIVF 回顾

IndexIVF 类（及其子类）适用于所有大规模Faiss场景。 它将所有输入向量分为 nlist 个组（nlist 是 IndexIVF 的一个字段）。 添加时，每个向量会被分配到一个组；查询时，会找到最接近查询向量的若干组并对其进行遍历扫描。

因此，IndexIVF 结构包含两个主要部分：

• 量化器（quantizer，也叫 coarse quantizer） 给定一个向量，量化器的查询函数会返回该向量所属的组（cluster）。如果查询时 nprobe>1，则返回距离查询向量最近的 nprobe 个组。

• 倒排列表对象 InvertedLists 用于将组编号（0..nlist-1）映射到一系列 (code, id) 对。

InvertedLists（倒排列表）对象

倒排列表中的code是定长字节串（code_size），比如IndexIVFFlat在36维时，code_size = 36 * sizeof(float) = 144字节。 id是64位整数（通常使用正数，负数保留作为特殊用途，实际可用63位）。

实际应用中，codes和ids会分别返回为两个数组。这样有些应用可以只需要其中之一，同时满足不同的内存对齐需求。

查询相关方法​

以下是对象的三个核心查询方法：

// 获取指定列表的元素数量
size_t list_size(size_t list_no);

// 返回 codes（大小为 list_size * code_size）
const uint8_t * get_codes (size_t list_no);
void release_codes (const uint8_t *codes) const;

// 返回 ids（大小为 list_size）
const idx_t * get_ids (size_t list_no);
void release_ids (const idx_t *ids) const;

此外还有 prefetch_lists 方法，用于在搜索前提前告知哪些倒排列表即将被访问，以提高效率。

典型的查询调用顺序如下：

search(v) {
    list_nos = quantizer->search(v, nprobe)
    invlists->prefetch(list_nos)
    foreach no in list_nos {
        codes = invlists->get_codes(no)
        // 对codes线性扫描
        // 选出最相似的codes
        ids = invlists->get_ids(no)
        // 将索引转换为id
        invlists->release_ids(ids)
        invlists->release_codes(codes)
    }
}

添加（add）相关方法​

添加向量需要对 InvertedLists 对象的读写访问。 add_entries 提供了基本写入方法。 另外还有 update_entries 和 resize 方法，适用于批量合并、拆分和删除操作。

倒排列表对象的行为说明

内存管理​

如果 IndexIVF 的 own_invlists 为 true，则在 IndexIVF 析构时会自动删除 InvertedLists 对象。 默认情况下，IndexIVF 实例化时会自动创建一个 ArrayInvertedLists 对象，并令 own_invlists 为 true。 你可以通过 replace_invlists 替换默认的 InvertedLists，此时需要自行决定对象的所有权。

多线程访问​

允许只读多线程访问。 关于并发读写访问，可参考代码中的注释说明。

输入输出（I/O）​

倒排列表对象可不必与索引对象一起存储。 若采用外部存储，只需在索引对象中存储用于处理外部存储的必要信息即可。

内置的 InvertedLists 类

InvertedLists 设计时就考虑了可扩展性。 但Faiss默认内置有以下几种倒排列表类型：

ArrayInvertedLists​

本质上是 std::vector<std::vector<...> > 的封装。 它是最简单的内存（RAM）倒排列表实现，开销极小、添加速度快。 构建 IndexIVF 时会自动生成该对象，支持直接添加向量。

OnDiskInvertedLists​

倒排列表数据存储在磁盘上的内存映射（memory-mapped）文件中。 存在一个间接表，将list id映射到文件中的偏移量。 由于数据采用内存映射方式，读取时无需显式从磁盘加载；不过 prefetch 方法依然有意义，便于在分布式文件系统上并行读取。

当你用 IO_FLAG_MMAP 标志调用 read_index 时，可以把 "普通" 的 IndexIVF 加载为 OnDiskInvertedLists，这样即便索引很大、不能全部装入内存，也能正常加载。

HStackInvertedLists 与 VStackInvertedLists​

这两个类可以将多个倒排列表对象组合成一个整体，使其表现为单一倒排列表对象。 名称来源于 numpy 的 hstack/vstack 操作，本质上倒排列表对象可视为稀疏矩阵。 HStack 将多个倒排列表合并，搜索会在合并后的所有倒排列表中进行。 VStack 假定有 k 个大小均为 nlist1 的倒排列表对象，将它们组合成一个大小为 nlist1 * k 的倒排列表对象。

InvertedListScanner（倒排列表扫描器）对象

倒排列表的扫描可以脱离Faiss主流程独立控制。 这样无需将倒排列表的访问实现为回调（callback），使用上更加灵活。

为此，Faiss提供：

• encode_vector 函数，可将向量编码为倒排列表的code，可用于填充非Faiss管理的自定义倒排列表；
• InvertedListScanner 对象，可从 IndexIVF 类获取，实现对列表的扫描，或者计算单个查询与编码之间的距离。

这种低级别（Low-level）的接口提供了完全的扫描控制权，无需像 InvertedLists 那样实现回调函数。

向量编码流程​

编码向量时，典型调用流程为：

• 使用量化器对向量分配倒排列表编号（list number）
• 调用 encode_vectors 对向量批量编码成code

以下示例展示如何将 nb 个向量（存于 xb）添加到自定义倒排列表：

// nb个待添加向量
idx_t *list_nos = ...;
// 为每个向量分配倒排列表编号
index_ivf.quantizer->assign(nb, xb, list_nos);

// 分配空间：大小 = code_size * nb
uint8_t *codes = ...;
// 计算所有向量的编码（codes）
index->encode_vectors(nb, xb, list_nos, codes);

// 填充自定义倒排列表
for (idx_t i = 0; i < nb; i++) {
    idx_t list_no = list_nos[i];
    // 为倒排列表list_no新分配一个元素
    // 获取新元素的id和code指针
    idx_t * id_ptr = ...;
    uint8_t * code_ptr = ...;
    // 假设向量编号依次递增
    *id_ptr = i;
    memcpy(code_ptr, codes + i * index->code_size, index->code_size);
}

示例详见：test_lowlevel_ivf.cpp (add)

搜索流程​

执行搜索时，包含多层循环。

下面举例查询了nq个待查向量（xq），其流程如下：

// 大小为 nprobe * nq
float * q_dis =  ...;
idx_t *q_lists = ...;
// 手动进行量化
index.quantizer->search(nq, xq, nprobe, q_dis, q_lists);

// 获取扫描器对象
scanner = index.get_InvertedListScanner();

// 分配结果数组（大小为 k * nq），并正确初始化
idx_t *I = ...;
float *D = ...;

// 遍历每一个查询
for (idx_t i = 0; i < nq; i++) {
    // 设置当前查询
    scanner->set_query(xq + i * d);

    // 遍历本次查询涉及的倒排列表
    for (int j = 0; j < nprobe; j++) {
        // 设置当前被扫描的倒排列表
        int list_no = q_lists[i * nprobe + j];
        scanner->set_list(list_no, q_dis[i * nprobe + j]);

        // 获取倒排列表的数据
        long list_size = ...;
        idx_t *ids = ...;
        uint8_t *codes = ...;
        // 执行扫描，更新结果
        scanner->scan_codes(list_size, codes, ids, D + i * k, I + i * k, k);
    }
    // 对堆结果按距离maxheap重排
    maxheap_reorder(k, D + i * k, I + i * k);
}

详细实现参考：test_lowlevel_ivf.cpp (search)