基于树的索引方法是一种数据结构，它以分层树格式组织向量，以实现高效的相似性搜索。这些方法将数据集划分为嵌套区域，允许搜索算法通过遍历树来快速缩小潜在匹配项的范围。与将查询向量与数据集中的每个向量进行比较（对于大型数据集来说速度很慢）不同，基于树的方法通过消除与查询无关的整个树分支来减少比较次数。这使得它们特别适用于推荐系统或聚类等应用中的最近邻搜索。
常见的例子包括 KD 树、球树和 Annoy (Approximate Nearest Neighbors Oh Yeah)。KD 树沿交替轴递归地分割数据集，创建超矩形区域。例如，在 2D 空间中，它可能会垂直分割数据，然后水平分割，依此类推。球树根据向量到质心的距离将向量分组为超球面（球），这可以更优雅地处理高维数据。Annoy 由 Spotify 开发，通过随机选择分割点构建二叉树森林，创建重叠区域以提高搜索准确性。每种方法都针对不同的权衡进行优化：KD 树适用于低维数据，球树更好地处理高维数据，而 Annoy 可以扩展到具有近似结果的大型数据集。
在选择基于树的方法时，开发人员必须考虑诸如数据集大小、维度和对近似结果的容忍度等因素。由于“维度诅咒”，KD 树在高维度上变得效率低下，而球树通过使用球形分区来缓解这种情况。Annoy 牺牲了准确性以换取速度，使其适用于推荐引擎等对近乎即时的结果至关重要的应用。诸如 scikit-learn（用于 KD 树和球树）和 Spotify 的 Annoy 实现之类的库提供了可访问的工具。但是，当添加新数据时，基于树的方法通常需要重建索引，这对于动态数据集来说可能是一个限制。对于具有适度维度的静态数据集，与散列或基于图的索引等替代方法相比，它们提供了简单性和性能的平衡。