HNSW 是一种图-based ANN 算法，构建一个多层图结构；
- 图结构：将向量表示为图中的节点，每层是一个小世界图（节点通过长/短边连接，形成高效导航路径）。顶层（高层）节点稀疏，用于快速粗粒度导航；底层（低层）节点密集，用于精细搜索。层数通常为 log(N)，其中 N 是向量数量。
- 高层（L2/L1）的点数量较少，底层（L0）保护全部点。
- 构建过程：插入向量时，从顶层开始贪婪搜索最近邻（efConstruction 参数控制候选邻居数），然后逐层下降，建立连接（每个节点的最大连接数为 M，通常 16～32）
- 搜索过程：查询从顶层入口点开始，贪婪遍历到局部最小点，然后下降到下一层，重复直到底层。在底层进行 beam search（梁搜索）精炼结果。时间复杂度约为 O(log N)，召回率高（可达 95%以上），但依赖内存随机访问。
- 估算：每个向量内存 ≈ 向量大小（d * 4 字节，d 为维度） + 图开销（2 * M * 4 字节指针）。
- M=16-32 时，每节点额外 128-256 字节。
- 1 百万 768 维向量：100w * 768 * 4 字节 + 100w * 2 * 16 * 4 字节 ≈2.98 GB，当前仅按最小来算，再加上元数据、数据结构对齐、其他辅助信息，内存占用会更高。
- M 越大，开销越高；高召回需更大 ef 参数，增加临时内存。
DiskANN 是微软开发/开源的磁盘优化 ANN 算法，基于 Vamana 图（一种扁平图结构，依然是图-base），旨在处理无法全载入内存的亿级数据集。它将索引存储在 SSD 上，仅在内存中保持压缩表示和导航结构。
- 图结构：使用 Vamana 算法构建扁平搜索图（非层次），节点对应向量或簇，边连接“相对接近”的节点。Vamana 通过剪枝（pruning）优化图：每个节点连接 R 个最近邻（搜索半径），然后保留 L 个最优邻居（平衡图直径和度）。为减少磁盘 I/O，先用 k-means 聚类数据，分别构建子图并合并。
- Vamana是单层图结构，可以添加更长的边。
- 构建过程：预处理阶段在内存中构建 Vamana 图，然后量化向量（使用产品量化 PQ 等压缩），全图和完整向量存储到 SSD。图布局优化为连续块存储相关节点，减少随机读。
- 搜索过程：分两阶段：(1) 在内存中用量化向量粗搜索 Vamana 图，找到候选节点（限制读入 SSD 的次数，通常 50-100 个）；(2) 从 SSD 读入完整向量精炼结果。使用缓存机制避免重复 I/O。时间复杂度 O(log N)，但受 SSD/NVME 磁盘延迟影响（毫秒级）。