[论文翻译]用于关联搜索的多维二叉搜索树

Multidimensional Binary Search Trees Used for Associative Searching 用于关联搜索的多维二叉搜索树 Jon Louis Bentley Stanford University Jon Louis Bentley Stanford University This paper develops the multidimensional binary search tree (or $\boldsymbol{k}$ d tree, where ... 本文提出了一种多维二叉搜索树（或称 \$\boldsymbol{k}\$ 维树，其中 \$\boldsymbol{k}\$ 表示搜索空间的维度）作为存储关联搜索信息的数据结构。论文定义了 \$k\$ 维树并提供了示例，其存储效率表现优异。该结构的显著优势在于：单一数据结构即可高效处理多种查询类型。研究开发了多种实用算法，经证明在 \$_n\$ 条记录文件中的平均运行时间为：插入操作 \$O(\log n)\$，根节点删除 \$O(n^{(k-1)/k})\$，随机节点删除 \$O(\log n)\$，优化操作（确保搜索对数性能）\$O(n\log n)\$。针对指定 t 个键的部分匹配查询[理论最坏运行时间 \$O(n^{(k-t)/k})\$]和最近邻查询[实证观测平均运行时间 \$O(\log n)\$]给出了搜索算法，其性能远超当前已知最优算法。同时提出了处理任意广义交集查询的算法。本文主要聚焦理论层面，但认为 \$k\$ 维树在诸多应用中具有重要潜力，并列举了潜在用例。