拓冰网站定制 
VexDB-Lite 自研图索引算法源码剖析层级结构、邻居选择与 MemStore 设计【免费下载链接】VexDB-LiteA cross-platform vector database, which can be integrated into existing databases as a plugin.项目地址: https://gitcode.com/gh_mirrors/ve/VexDB-LiteVexDB-Lite 是一个跨平台向量数据库以插件形式集成进 PostgreSQL、DuckDB、SQLite 等现有数据库。它的核心是一套自研的图索引Graph Index算法借鉴了 HNSW 的多层导航思路又针对并发构建、磁盘存储和量化压缩做了深度定制。本文从源码层面拆解三块关键设计多层级图结构如何分层、新点插入时邻居如何裁剪选择、以及内存构建池 MemStore 如何支撑万级并发写入。无需阅读大段代码我们只讲清为什么这么设计。对 AI Agent 而言向量数据库就是它的长期记忆Memory检索越快Agent 响应越快而图索引正是检索提速的关键。一、层级结构像大楼一样的多层导航图图索引的第一层直觉是高速公路 国道上层点稀疏、边短距离跳跃下层点稠密、边短距离微调。VexDB-Lite 完全实现了这一思路且有一个硬上限层数上限 16宏GRAPH_INDEX_MAX_LEVEL定义在 graph_index_param.h防止极端情况下层数失控。随机指数分布抽层每个新点以概率分布决定住几层楼公式就是经典的-ln(R) / ln(m)实现在 graph_index_algorithm.h 的get_insert_level()中。m越大高楼层越少——上层越空旷导航越快。入口点entry point图元数据页GraphIndexMetaPageData保存entry_level、entrypoint_id等入口信息。搜索永远从最高层的入口点出发逐层下楼梯直到第 0 层base 层做精细化搜索。层与层之间的差异还有一个细节base 层每个点最多保留2m个邻居上层只保留m个见 graph_index_algorithm.h 的get_nbr_num()。底层是最后冲刺需要更宽的候选网来保证召回率。二、邻居选择双向裁剪保证图不堵车邻居选择是 HNSW 类算法的灵魂。VexDB-Lite 实现了双向选择1. 正向选择新点挑邻居forward pruning新点插入 base 层时先在图上搜到ef_construction个候选邻居再从中挑选最终的2m个。裁剪规则在 select_neighbors() 中按距离从近到远遍历候选点一个候选点只有当它比自己到已选邻居的距离更靠近自己时才被保留——这保证了保留的邻居在空间上尽量分散而不是全挤在一个局部区域里如果裁剪后名额未满被丢弃的点会按顺序回填确保每个点的邻居槽位尽量填满。这种罗盘式启发式让图的出边覆盖更广方向搜索时不容易走进死胡同。2. 反向更新老邻居给新点让位reverse edge update插入不止是新点指老点老点也要指回来。update_reverse_edges() 对每个被选中的邻居加锁把新点加入其邻居列表若列表已满则通过第二个重载的select_neighbors()第 765 行起找出**最不值得保留的旧邻居**将其替换掉——被替换者通常是那个距离自己太远、对导航贡献最小的点。这套双向机制保证了图在持续写入中始终保持连通与均衡无需周期性重建。三、搜索流程两个优先队列的经典博弈search_layer()graph_index_algorithm.h用两个优先队列完成单层搜索队列作用弹出规则closest小顶堆待扩展的候选点弹出最近的点继续扩展furthest大顶堆容量ef当前最优的 ef 个结果最差点作为剪枝阈值当前点比ef个结果中最远的还要远时搜索立刻终止——这就是ef_search参数控制精度 vs 速度的旋钮默认 40见 graph_index_param.h。上层搜索则退化为ef 1的贪心下降search_upper_layer()每层只保留最近的 1 个点纯做导航几乎不做精度计算。上层走高速、base 层走街巷各司其职。另外当索引启用了 PQ/RaBitQ 等量化压缩时算法会自动把ef_search放大 1.25 倍并用原始向量做refine()精排search_internal()用少量额外计算换回召回率。四、MemStore 设计为并发构建而生的内存池MemStore 是构建期的纯内存存储设计目标只有四个字并发不锁。核心手法三个分池vector_pool向量本体、basepoint_poolbase 层邻居表、upperpoint_pool上层点。向量与邻居分离存放缓存行利用率更高。Chunk 化内存池MemPool 把内存切成 2 的幂大小的 chunk预分配 chunk 槽位数组读取路径get()完全无锁仅在扩展新 chunk 时短暂加互斥锁。每点细粒度读写锁每个 chunk 配一把RWBitLock位图锁同一 chunk 内不同点互不阻塞点级并行构建得以成立。原子 ID 分配assign_vector_id()用fetch_add无锁取号graph_index_storage.h。架构级内存序修复注释中记录了 aarch64 弱内存模型下槽位先于内容可见导致的并行构建段错误通过先构造、release fence、再发布_end的顺序修复extend()。距离缓存策略差异化MemStore 令use_dist_cache false距离直接算内存里算一次很便宜而运行期的 DiskStore 用哈希表缓存点对距离避免重复读盘。构建期若内存不足MemStore 会把已积累的数据刷出到 DiskStore 继续构建设计约定见 graph_index_storage.h 的头部注释保证大索引构建不因 OOM 失败。DuckDB 侧则通过 vex_duck_memstore.hpp 提供适配层复用同一套算法核心。五、关键参数速查表参数默认值范围含义m162 ~ 100每个点的最大邻居数上层base 层为 2mef_construction644 ~ 1000建图时搜索候选宽度越大图质量越高、构建越慢ef_search401 ~ 1000查询时候选宽度越大召回越高、越慢parallel_workers-1 ~ 1024并行构建 worker 数常量定义集中在 graph_index_param.h运行时选项结构见 GraphIndexOptions。六、小结VexDB-Lite 的图索引把 HNSW 的三个关键点都做足了工程化层级结构——16 层上限 指数分布抽层 逐层下降导航兼顾跳远与精搜邻居选择——正向空间分散裁剪 反向最弱者替换图在持续写入下保持均衡MemStore——分池、chunk 化、位图锁与原子取号让建图可以高并发且无全局锁同时以 OOM 刷盘兜底。配合 PQ / RaBitQ 量化与 refine 精排同一套算法核心可以在内存、磁盘、压缩三种形态间切换这正是它作为可嵌入插件跨 PostgreSQL / DuckDB / SQLite 三个后端复用的底气。想深入阅读建议从 common/include/graph_index/ 目录下的 graph_index.h 总入口开始再到 vexdb_pg/src/graph_index/ 查看 PostgreSQL 侧的构建与扫描实现。【免费下载链接】VexDB-LiteA cross-platform vector database, which can be integrated into existing databases as a plugin.项目地址: https://gitcode.com/gh_mirrors/ve/VexDB-Lite创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 VexDB-Lite 自研图索引算法源码剖析：层级结构、邻居选择与 MemStore 设计
VexDB-Lite 自研图索引算法源码剖析层级结构、邻居选择与 MemStore 设计【免费下载链接】VexDB-LiteA cross-platform vector database, which can be integrated into existing databases as a plugin.项目地址: https://gitcode.com/gh_mirrors/ve/VexDB-LiteVexDB-Lite 是一个跨平台向量数据库以插件形式集成进 PostgreSQL、DuckDB、SQLite 等现有数据库。它的核心是一套自研的图索引Graph Index算法借鉴了 HNSW 的多层导航思路又针对并发构建、磁盘存储和量化压缩做了深度定制。本文从源码层面拆解三块关键设计多层级图结构如何分层、新点插入时邻居如何裁剪选择、以及内存构建池 MemStore 如何支撑万级并发写入。无需阅读大段代码我们只讲清为什么这么设计。对 AI Agent 而言向量数据库就是它的长期记忆Memory检索越快Agent 响应越快而图索引正是检索提速的关键。一、层级结构像大楼一样的多层导航图图索引的第一层直觉是高速公路 国道上层点稀疏、边短距离跳跃下层点稠密、边短距离微调。VexDB-Lite 完全实现了这一思路且有一个硬上限层数上限 16宏GRAPH_INDEX_MAX_LEVEL定义在 graph_index_param.h防止极端情况下层数失控。随机指数分布抽层每个新点以概率分布决定住几层楼公式就是经典的-ln(R) / ln(m)实现在 graph_index_algorithm.h 的get_insert_level()中。m越大高楼层越少——上层越空旷导航越快。入口点entry point图元数据页GraphIndexMetaPageData保存entry_level、entrypoint_id等入口信息。搜索永远从最高层的入口点出发逐层下楼梯直到第 0 层base 层做精细化搜索。层与层之间的差异还有一个细节base 层每个点最多保留2m个邻居上层只保留m个见 graph_index_algorithm.h 的get_nbr_num()。底层是最后冲刺需要更宽的候选网来保证召回率。二、邻居选择双向裁剪保证图不堵车邻居选择是 HNSW 类算法的灵魂。VexDB-Lite 实现了双向选择1. 正向选择新点挑邻居forward pruning新点插入 base 层时先在图上搜到ef_construction个候选邻居再从中挑选最终的2m个。裁剪规则在 select_neighbors() 中按距离从近到远遍历候选点一个候选点只有当它比自己到已选邻居的距离更靠近自己时才被保留——这保证了保留的邻居在空间上尽量分散而不是全挤在一个局部区域里如果裁剪后名额未满被丢弃的点会按顺序回填确保每个点的邻居槽位尽量填满。这种罗盘式启发式让图的出边覆盖更广方向搜索时不容易走进死胡同。2. 反向更新老邻居给新点让位reverse edge update插入不止是新点指老点老点也要指回来。update_reverse_edges() 对每个被选中的邻居加锁把新点加入其邻居列表若列表已满则通过第二个重载的select_neighbors()第 765 行起找出**最不值得保留的旧邻居**将其替换掉——被替换者通常是那个距离自己太远、对导航贡献最小的点。这套双向机制保证了图在持续写入中始终保持连通与均衡无需周期性重建。三、搜索流程两个优先队列的经典博弈search_layer()graph_index_algorithm.h用两个优先队列完成单层搜索队列作用弹出规则closest小顶堆待扩展的候选点弹出最近的点继续扩展furthest大顶堆容量ef当前最优的 ef 个结果最差点作为剪枝阈值当前点比ef个结果中最远的还要远时搜索立刻终止——这就是ef_search参数控制精度 vs 速度的旋钮默认 40见 graph_index_param.h。上层搜索则退化为ef 1的贪心下降search_upper_layer()每层只保留最近的 1 个点纯做导航几乎不做精度计算。上层走高速、base 层走街巷各司其职。另外当索引启用了 PQ/RaBitQ 等量化压缩时算法会自动把ef_search放大 1.25 倍并用原始向量做refine()精排search_internal()用少量额外计算换回召回率。四、MemStore 设计为并发构建而生的内存池MemStore 是构建期的纯内存存储设计目标只有四个字并发不锁。核心手法三个分池vector_pool向量本体、basepoint_poolbase 层邻居表、upperpoint_pool上层点。向量与邻居分离存放缓存行利用率更高。Chunk 化内存池MemPool 把内存切成 2 的幂大小的 chunk预分配 chunk 槽位数组读取路径get()完全无锁仅在扩展新 chunk 时短暂加互斥锁。每点细粒度读写锁每个 chunk 配一把RWBitLock位图锁同一 chunk 内不同点互不阻塞点级并行构建得以成立。原子 ID 分配assign_vector_id()用fetch_add无锁取号graph_index_storage.h。架构级内存序修复注释中记录了 aarch64 弱内存模型下槽位先于内容可见导致的并行构建段错误通过先构造、release fence、再发布_end的顺序修复extend()。距离缓存策略差异化MemStore 令use_dist_cache false距离直接算内存里算一次很便宜而运行期的 DiskStore 用哈希表缓存点对距离避免重复读盘。构建期若内存不足MemStore 会把已积累的数据刷出到 DiskStore 继续构建设计约定见 graph_index_storage.h 的头部注释保证大索引构建不因 OOM 失败。DuckDB 侧则通过 vex_duck_memstore.hpp 提供适配层复用同一套算法核心。五、关键参数速查表参数默认值范围含义m162 ~ 100每个点的最大邻居数上层base 层为 2mef_construction644 ~ 1000建图时搜索候选宽度越大图质量越高、构建越慢ef_search401 ~ 1000查询时候选宽度越大召回越高、越慢parallel_workers-1 ~ 1024并行构建 worker 数常量定义集中在 graph_index_param.h运行时选项结构见 GraphIndexOptions。六、小结VexDB-Lite 的图索引把 HNSW 的三个关键点都做足了工程化层级结构——16 层上限 指数分布抽层 逐层下降导航兼顾跳远与精搜邻居选择——正向空间分散裁剪 反向最弱者替换图在持续写入下保持均衡MemStore——分池、chunk 化、位图锁与原子取号让建图可以高并发且无全局锁同时以 OOM 刷盘兜底。配合 PQ / RaBitQ 量化与 refine 精排同一套算法核心可以在内存、磁盘、压缩三种形态间切换这正是它作为可嵌入插件跨 PostgreSQL / DuckDB / SQLite 三个后端复用的底气。想深入阅读建议从 common/include/graph_index/ 目录下的 graph_index.h 总入口开始再到 vexdb_pg/src/graph_index/ 查看 PostgreSQL 侧的构建与扫描实现。【免费下载链接】VexDB-LiteA cross-platform vector database, which can be integrated into existing databases as a plugin.项目地址: https://gitcode.com/gh_mirrors/ve/VexDB-Lite创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考