具有多个键和范围搜索支持的树图

Question

我需要一个高效的数据结构来保存对到值的映射

(x,y) => v

并允许查找匹配二维范围表达式的键值对：

x1 < x < x2 && y1 < y < y2

比完整搜索更快。我有一些解决方案，尽管实施起来很繁重。这样的任务有什么标准algorithm/approach吗？我相信数据库开发人员在解决复合索引问题时必须解决这个问题。

Answer 1

如果你想要一个非常简单的解决方案，试试这个：

• 保持键在 x 上排序；

• 给定一个查询范围，通过二分法找到x范围内的第一个点；

• 在 x 上循环直到 x 范围结束并在 y 上测试。

假设您的密钥均匀分布，如果 x 范围占据整个域的一小部分 Fx，则与穷举搜索相比的加速是 1/Fx（不幸的是，不是 1/Fx.Fy）。

尽管收益可能看起来微不足道，但值得实施它以将其与穷举搜索和您可以尝试的任何更复杂的方法进行比较。

---

另一个简单的解决方案是 网格化，即将点存储在与每个网格单元关联的链表中。然后可以将搜索限制在与范围重叠的单元格中。

您需要在单元格大小上找到一个好的折衷方案；比范围的典型大小大得多的单元格是低效的；但是细胞太小以至于大部分都是空的也是低效的。

四叉树数据结构可以看作是网格化的自适应版本。