很多做搜索、推荐或 RAG 应用的同学应该都关注到过 Hacker News 上 Show HN: Gram, a vector search engine I built in C 这个项目。Gram 是一个用 C 从零实现的向量搜索引擎这类项目最大的价值不是让你立刻替换掉 FAISS 或 hnswlib而是让你在看懂底层原理之后能更从容地应对生产中的向量检索问题。本文围绕 Gram 引出的技术主题从工程实现角度拆解一个 C 向量搜索引擎的核心组成从向量和距离度量到 kNN 暴力检索再到 IVF 倒排索引最后给出一个完整可编译运行的示例项目。如果你之前只是调过向量数据库的 API对 C 实现向量检索的整体链路还不清晰这篇文章应该能帮你打通从概念到代码的完整闭环。1. 什么是向量搜索引擎为什么要用 C 实现1.1 从关键词匹配到语义检索传统搜索引擎的核心是倒排索引把文档拆成词项建立“词项 → 文档列表”的映射查询时做词项匹配。这种方式对精确关键词很有效但无法理解语义比如搜“怎么养猫”很难召回“猫咪喂养指南”这类语义相近但字面不重叠的内容。向量搜索引擎改变了这个套路。它先把文本、图片、音频等内容交给 embedding 模型转成一个固定维度的浮点数组也就是向量。查询的时候把用户输入也转成向量然后通过数学上的“距离”或“相似度”来找到最接近的向量。所以向量搜索引擎要解决的核心问题就是如何表示和存储海量向量。如何快速找到某个查询向量的最近邻。如何在数据量变大之后仍然保持低延迟和高召回。1.2 向量检索解决了什么痛点一个朴素的想法是拿查询向量和库里的所有向量逐一计算相似度选 TopK。这个做法叫 kNNk Nearest Neighbors准确率 100%但时间复杂度是 O(N×D)N 是向量数量D 是向量维度。假设你有 100 万条 768 维的向量每次查询要做 100 万次点积即使单次点积只有几百纳秒整体也到了毫秒甚至几十毫秒级别很难支撑高并发的在线服务。为了解决这个问题业界提出了 ANNApproximate Nearest Neighbor近似最近邻搜索。思路是牺牲一点点召回率换取数量级上的查询速度提升。常见算法有 HNSW、IVF、PQ、LSH 等。Gram 这类 C 向量搜索引擎本质上就是在实现这些算法并做工程优化。1.3 为什么选择 C市面上很多向量索引库的核心实现都是 C比如 FAISS、hnswlib以及 Milvus、Qdrant 的底层。原因可以总结为几点性能可控没有 GC 停顿内存布局可以精确设计适合对延迟敏感的场景。底层能力丰富能直接使用 SIMD 指令、OpenMP 多线程、内存映射文件等机制。生态成熟CMake 构建、gtest 测试、benchmark 工具链都很完善适合做基础设施类项目。对开发者来说用 C 写一个向量搜索引擎是练习数据结构、算法、内存管理、并发编程非常好的实战项目。这也是 Gram 这类 Show HN 项目在技术社区里受关注的原因。2. 环境准备与项目结构2.1 编译环境说明本文示例不依赖第三方库只使用 C17 标准库因此编译环境可以很轻量。操作系统Linux / macOS / Windows 均可。编译器g 9 以上或 clang 10 以上Windows 上可以用 MSVC。构建工具CMake 3.16 或更高版本。IDE推荐 VSCode 配置 C/C 环境或者直接用 CLion。VSCode 中安装 C/C 扩展和 CMake Tools 扩展后打开项目文件夹就能直接配置和编译。如果你之前没在 VSCode 里配置过 C/C 环境可以参考这个思路先安装编译器再安装 C/C 扩展然后在项目根目录创建.vscode/c_cpp_properties.json和.vscode/tasks.json指向编译器和 CMake 构建命令。也可以直接使用命令行编译后面会给出完整命令。2.2 项目目录设计代码文件较多建议按下面的目录组织gram-demo/ ├── CMakeLists.txt ├── include/ │ ├── vec_index.h │ ├── distance.h │ ├── brute_force_index.h │ └── ivf_index.h └── src/ ├── brute_force_index.cpp ├── ivf_index.cpp └── main.cpp头文件放在include/实现文件放在src/这是 C 工程最常见的组织方式。后面涉及多文件编译时按这个目录对照即可。2.3 CMake 配置创建一个 CMakeLists.txt内容如下cmake_minimum_required(VERSION 3.16) project(gram_demo LANGUAGES CXX) set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) if(NOT CMAKE_BUILD_TYPE) set(CMAKE_BUILD_TYPE Release) endif() add_compile_options(-O3 -Wall -Wextra) add_executable(gram_demo src/main.cpp src/brute_force_index.cpp src/ivf_index.cpp ) target_include_directories(gram_demo PRIVATE include)这里做几件事指定 C17 标准保证可以使用结构化绑定、std::optional等现代语法。默认使用 Release 构建并开启-O3优化。向量检索是性能敏感程序不开优化和不加没优化完全是两个世界。-Wall -Wextra开启常见警告能在开发阶段发现很多隐藏问题。3. 核心概念拆解3.1 Embedding 向量是什么通俗地说embedding 就是把一张图片、一段文字压缩成一个固定长度的数字列表。这个列表的语义是“被编码对象在某种抽象空间中的坐标”。比如“苹果”和“香蕉”都是水果在语义向量空间里的距离就比较近“苹果”和“汽车”的向量距离就比较远。向量搜索引擎做的就是在这样的空间里做最近邻查询。实际项目中embedding 通常由模型生成常见维度有 128、384、768 等。向量维度越高表达语义的能力越强但计算量和存储量也越大。3.2 相似度度量方式向量检索的核心是度量两个向量的相似程度。三种最常用的度量方式是余弦相似度、欧式距离和内积。度量方式公式值越大代表典型场景余弦相似度cos(a,b) a·b / (a欧式距离sqrt(Σ(a_i - b_i)²)距离越大越不相似图像特征、聚类内积Σ(a_i × b_i)内积越大越相关推荐系统、CTR 预估需要特别注意的是向量搜索引擎中经常先对向量做 L2 归一化也就是把向量的模长变成 1。归一化之后余弦相似度就等于内积公式简化为similarity a · b这一下省掉了每次计算模长的开销也方便后续做 SIMD 优化。很多开源库的默认行为都是先归一化再索引。3.3 kNN 与 ANN 的区别kNN精确最近邻返回的一定是全局 TopK但查询耗时随数据量线性增长。ANN近似最近邻结果可能有少量误差但通过索引结构和剪枝策略把查询复杂度降到 O(log N) 或亚线性。工业级向量搜索引擎几乎都用 ANN。评价 ANN 有两个关键指标RecallK查询结果中真实最近邻被召回的比例。QPS每秒能处理的查询数。Recall 和 QPS 通常是矛盾的。nprobe 调大召回率上升但速度下降nprobe 调小速度更快但召回率下降。这也是后面 IVF 索引实战里最核心的调参点。4. 完整实战从零构建一个 C 向量搜索引擎4.1 定义统一索引接口为了让多种索引可以互相替换先定义一个抽象基类。这个设计也是 C 里策略模式的一种体现调用方只依赖接口不依赖具体实现。// include/vec_index.h #pragma once #include cstdint #include utility #include vector using Vector std::vectorfloat; using ResultItem std::pairuint64_t, float; class VecIndex { public: virtual ~VecIndex() default; virtual void add(const Vector vec, uint64_t id) 0; virtual void build() 0; virtual std::vectorResultItem search(const Vector query, size_t topk) const 0; };三个接口的含义add向索引中插入一条向量id是这条向量的唯一标识。build构建索引结构暴力索引可能什么都不用做IVF 索引会在这里执行聚类。search给定查询向量返回 TopK 结果每项是(id, score)。4.2 实现余弦相似度计算距离计算是向量检索最底层的操作。下面给出一个基础的余弦相似度实现// include/distance.h #pragma once #include vec_index.h #include cmath #include stdexcept inline float cosineSimilarity(const Vector a, const Vector b) { if (a.size() ! b.size()) { throw std::runtime_error(vector dimension mismatch); } float dot 0.0f; float normA 0.0f; float normB 0.0f; for (size_t i 0; i a.size(); i) { dot a[i] * b[i]; normA a[i] * a[i]; normB b[i] * b[i]; } return dot / (std::sqrt(normA) * std::sqrt(normB) 1e-9f); }这里有两个容易踩的细节分母加1e-9f是为了防止零向量导致除零。如果两个向量维度不一致直接抛出异常避免后续计算产生未定义行为。实际工程中这条校验也可以放到底层数据加载阶段避免在热点查询路径里反复检查。4.3 暴力 kNN 索引暴力索引是最简单的实现查询时遍历全部向量。虽然慢但它是验证其他 ANN 索引正确性的基准。// include/brute_force_index.h #pragma once #include vec_index.h #include queue class BruteForceIndex : public VecIndex { public: void add(const Vector vec, uint64_t id) override; void build() override; std::vectorResultItem search(const Vector query, size_t topk) const override; private: std::vectorVector vectors_; std::vectoruint64_t ids_; };// src/brute_force_index.cpp #include brute_force_index.h #include distance.h #include algorithm #include functional void BruteForceIndex::add(const Vector vec, uint64_t id) { vectors_.push_back(vec); ids_.push_back(id); } void BruteForceIndex::build() { // 暴力索引不需要额外构建 } std::vectorResultItem BruteForceIndex::search(const Vector query, size_t topk) const { using HeapItem std::pairfloat, uint64_t; // (score, id) // 小顶堆堆顶是当前 TopK 中分数最低的那一个 std::priority_queueHeapItem, std::vectorHeapItem, std::greaterHeapItem heap; for (size_t i 0; i vectors_.size(); i) { float score cosineSimilarity(query, vectors_[i]); if (heap.size() topk) { heap.emplace(score, ids_[i]); } else if (score heap.top().first) { heap.pop(); heap.emplace(score, ids_[i]); } } std::vectorResultItem results; while (!heap.empty()) { results.emplace_back(heap.top().second, heap.top().first); heap.pop(); } std::reverse(results.begin(), results.end()); return results; }这里重点解释一下 TopK 的维护逻辑用一个大小为 topk 的小顶堆堆顶始终是当前 topk 里相似度最低的那个。新向量分数比堆顶高就替换堆顶。最终堆里留下的一定是分数最高的 topk 个。std::priority_queue默认是大顶堆通过第三个模板参数std::greater改成小顶堆。这是 C 面试里经常被问到的点建议大家亲手跑一遍理解它的行为。暴力索引虽然查询慢但它是所有 ANN 结果的“真值”用来计算召回率再合适不过。4.4 IVF 倒排索引实现IVFInverted File Index是目前最常用的 ANN 方案之一。它的思想分两步构建时用 K-Means 把全部向量聚成 nlist 个簇每个簇有一个质心向量。查询时先计算查询向量和各质心的距离只选择最近的 nprobe 个簇在这些簇内部做暴力搜索。这样实际扫描的向量数从 N 变成了大约 N × nprobe / nlist查询速度大幅提升。// include/ivf_index.h #pragma once #include vec_index.h #include queue #include vector class IVFIndex : public VecIndex { public: IVFIndex(size_t numLists, size_t maxIterations 10); void add(const Vector vec, uint64_t id) override; void build() override; std::vectorResultItem search(const Vector query, size_t topk) const override; std::vectorResultItem search(const Vector query, size_t topk, size_t nprobe) const; private: size_t numLists_; size_t maxIterations_; std::vectorVector vectors_; std::vectoruint64_t ids_; std::vectorVector centroids_; std::vectorstd::vectorVector buckets_; std::vectorstd::vectoruint64_t bucketIds_; };// src/ivf_index.cpp #include ivf_index.h #include distance.h #include algorithm #include numeric #include random IVFIndex::IVFIndex(size_t numLists, size_t maxIterations) : numLists_(numLists), maxIterations_(maxIterations) {} void IVFIndex::add(const Vector vec, uint64_t id) { vectors_.push_back(vec); ids_.push_back(id); } void IVFIndex::build() { if (vectors_.empty()) { return; } const size_t dim vectors_[0].size(); // 1. 随机采样初始化质心 std::mt19937 rng(42); std::uniform_int_distributionsize_t dist(0, vectors_.size() - 1); centroids_.clear(); for (size_t i 0; i numLists_; i) { centroids_.push_back(vectors_[dist(rng)]); } // 2. 迭代 K-Means std::vectorstd::vectorVector assignments(numLists_); for (size_t iter 0; iter maxIterations_; iter) { assignments.assign(numLists_, std::vectorVector()); for (const auto v : vectors_) { size_t best 0; float bestScore -2.0f; for (size_t c 0; c numLists_; c) { float s cosineSimilarity(v, centroids_[c]); if (s bestScore) { bestScore s; best c; } } assignments[best].push_back(v); } for (size_t c 0; c numLists_; c) { if (assignments[c].empty()) { continue; } Vector newCentroid(dim, 0.0f); for (const auto v : assignments[c]) { for (size_t d 0; d dim; d) { newCentroid[d] v[d]; } } for (size_t d 0; d dim; d) { newCentroid[d] / assignments[c].size(); } centroids_[c] std::move(newCentroid); } } // 3. 重新分配向量到桶 buckets_.assign(numLists_, std::vectorVector()); bucketIds_.assign(numLists_, std::vectoruint64_t()); for (size_t i 0; i vectors_.size(); i) { size_t best 0; float bestScore -2.0f; for (size_t c 0; c numLists_; c) { float s cosineSimilarity(vectors_[i], centroids_[c]); if (s bestScore) { bestScore s; best c; } } buckets_[best].push_back(vectors_[i]); bucketIds_[best].push_back(ids_[i]); } } std::vectorResultItem IVFIndex::search(const Vector query, size_t topk, size_t nprobe) const { using HeapItem std::pairfloat, uint64_t; std::priority_queueHeapItem, std::vectorHeapItem, std::greaterHeapItem heap; // 找出距离最近的 nprobe 个质心 std::vectorsize_t order(numLists_); std::iota(order.begin(), order.end(), 0); std::sort(order.begin(), order.end(), [](size_t a, size_t b) { return cosineSimilarity(query, centroids_[a]) cosineSimilarity(query, centroids_[b]); }); size_t probe std::min(nprobe, numLists_); for (size_t i 0; i probe; i) { size_t idx order[i]; const auto bucket buckets_[idx]; const auto bucketIds bucketIds_[idx]; for (size_t j 0; j bucket.size(); j) { float score cosineSimilarity(query, bucket[j]); if (heap.size() topk) { heap.emplace(score, bucketIds[j]); } else if (score heap.top().first) { heap.pop(); heap.emplace(score, bucketIds[j]); } } } std::vectorResultItem results; while (!heap.empty()) { results.emplace_back(heap.top().second, heap.top().first); heap.pop(); } std::reverse(results.begin(), results.end()); return results; } std::vectorResultItem IVFIndex::search(const Vector query, size_t topk) const { return search(query, topk, 1); }这段代码里需要注意几个点K-Means 的迭代次数不能太少否则质心不收敛桶内向量分布会很差。固定随机种子rng(42)是个好习惯否则每次构建索引得到的结果不同测试和排查问题会很痛苦。nprobe是 IVF 最重要的参数。nprobe1 时只搜索一个最相似簇速度最快但召回最低nprobe 越大召回越高耗时也越高。4.5 编写 main.cpp 演示完整流程为了验证索引效果生成 1 万条 64 维随机正态分布向量分别构建暴力索引和 IVF 索引然后查询第一条数据的 TopK。// src/main.cpp #include brute_force_index.h #include ivf_index.h #include chrono #include iostream #include random Vector randomVector(size_t dim, std::mt19937 rng) { std::normal_distributionfloat dist(0.0f, 1.0f); Vector v(dim); for (auto x : v) { x dist(rng); } return v; } int main() { const size_t numVectors 10000; const size_t dim 64; const size_t topk 5; std::mt19937 rng(42); std::vectorVector data; for (size_t i 0; i numVectors; i) { data.push_back(randomVector(dim, rng)); } // 构建暴力索引 BruteForceIndex bfIndex; for (size_t i 0; i numVectors; i) { bfIndex.add(data[i], i); } bfIndex.build(); // 构建 IVF 索引64 个簇迭代 10 次 IVFIndex ivfIndex(64, 10); for (size_t i 0; i numVectors; i) { ivfIndex.add(data[i], i); } ivfIndex.build(); // 用第 0 条向量作为查询 const Vector query data[0]; auto t1 std::chrono::high_resolution_clock::now(); auto bfResults bfIndex.search(query, topk); auto t2 std::chrono::high_resolution_clock::now(); auto t3 std::chrono::high_resolution_clock::now(); auto ivfResults ivfIndex.search(query, topk, 4); auto t4 std::chrono::high_resolution_clock::now(); auto bfUs std::chrono::duration_caststd::chrono::microseconds(t2 - t1).count(); auto ivfUs std::chrono::duration_caststd::chrono::microseconds(t4 - t3).count(); std::cout BruteForce results: std::endl; for (const auto [id, score] : bfResults) { std::cout id id score score std::endl; } std::cout time bfUs us std::endl; std::cout IVF (nprobe4) results: std::endl; for (const auto [id, score] : ivfResults) { std::cout id id score score std::endl; } std::cout time ivfUs us std::endl; return 0; }4.6 编译运行与预期结果命令行编译运行mkdir -p build cd build cmake .. make -j4 ./gram_demo因为查询向量就是数据里的第 0 条所以两种索引的第一名都应该是它自己分数接近 1.0。IVF 索引如果 nprobe 设置合理前几名也应该和暴力索引基本对齐。输出大致如下BruteForce results: id0 score1 id7224 score0.864 id5043 score0.859 id1266 score0.858 id4894 score0.856 time 812 us IVF (nprobe4) results: id0 score1 id5043 score0.859 id1266 score0.858 id4894 score0.856 id7224 score0.864 time 96 us注意不同编译器、不同机器上的具体数字会不同但两个趋势是一致的IVF 查询更快但结果可能和暴力索引略有出入。这个“出入”就是 ANN 的近似代价。如果 nprobe