algorithm - 具有多个键和范围搜索支持的 TreeMap

Question

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

(x,y) => v

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

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

比完整搜索更快。我有一些解决方案，尽管实现起来很繁重。是否有针对此类任务的标准算法/方法？我相信数据库开发人员必须在解决复合索引问题的同时解决这个问题。

Answer 1

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

• 保持键在 x 上排序；

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

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

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

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

---

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

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

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