基于树的索引（例如 Annoy 的随机投影森林）和基于图的索引（例如 HNSW）在组织数据和执行搜索的方式上有所不同，从而导致在速度和召回率方面存在不同的权衡。基于树的方法使用决策边界（例如，随机超平面）以分层方式划分数据，而基于图的方法将数据点之间的关系建模为相互连接的节点。 这些结构差异直接影响其性能特征。
在搜索速度方面，基于树的索引通常具有可预测的延迟，因为它们遍历固定的分层结构。例如，Annoy 构建多个二叉树，每次搜索都涉及下降到每棵树的叶节点并聚合结果。然而，查询多个树（以提高召回率）的需求会增加计算开销。 相比之下，像 HNSW 这样的基于图的方法使用图的层次结构，其中搜索从粗糙的层开始，并在更精细的层中细化结果。 这种“放大”方法使 HNSW 能够快速跳过不相关的区域，通常可以缩短搜索时间，尤其是在高维空间中。 例如，对于相同的召回率，HNSW 可能需要比 Annoy 更少的距离计算，因为图边缘直接编码邻近关系。
召回率差异源于每种方法处理“维度灾难”的能力。 基于树的索引依赖于划分，这在高维数据中可能会遇到困难，因为超平面可能会分割自然聚类，从而导致错过邻居。 Annoy 通过使用多个树（减少方差）来缓解此问题，但增加树的数量会降低搜索速度。 另一方面，HNSW 在高维度上更有效地保持召回率，因为它的图层保留了局部和长程连接。 例如，HNSW 的“小世界”属性确保任何节点都可以在少量步骤内到达，从而降低了忽略真实最近邻居的风险。 在基准测试中，与 Annoy 相比，HNSW 通常在相似的速度水平下实现更高的召回率，尤其是在数据集较大或维度超过 100 时。
实际考虑因素进一步突出了这些差异。 Annoy 更易于实现，需要的内存更少，因此适用于索引构建时间或资源约束重要的场景。 例如，拥有中等大小数据集（例如，50D 中的 1M 嵌入）的开发人员可能更喜欢 Annoy，因为它在速度和简单性之间取得了平衡。 虽然 HNSW 调整起来更复杂（例如，管理层数和边缘连接），但它在高吞吐量应用（如大规模推荐系统）中表现出色，在这些应用中，亚毫秒级延迟和 >95% 的召回率至关重要。 最终的选择取决于问题的维度、数据集大小以及对速度和准确性之间权衡的容忍度。