几何与区间：空间的架构

维度的诅咒

给数字排序很容易。5 比 3 大吗？是的。 但给空间排序很难。(5, 3) 比 (4, 8) 大吗？这取决于你怎么看。

当数据拥有多个维度（经度/纬度、开始时间/结束时间、X/Y/Z）时，简单的列表就不够用了。如果你想找到“最近的加油站”或者“所有与下午 2 点重叠的会议”，你不能简单地扫描一个有序数组。

本章的主题是 空间索引 (Spatial Indexing)。这是一门将空间（和时间）划分为可管理层级的艺术，让我们能以有限的速度查询无限的平面。

分区的策略

在本章中，我们将从一维的线迈向 N 维的世界：

空间的三大法则

1. 层级 (Hierarchy)： 为了高效搜索空间，你必须将空旷的区域聚合在一起。如果一个大盒子是空的，你就没必要往里看。
2. 重叠 (Overlap)： 与数字排序不同，空间物体可以重叠。一个健壮的算法必须能处理“同时处于两个地方”的模糊性。
3. 诅咒 (The Curse)： 随着维度增加，距离变得毫无意义。在 1000 维空间中，任何东西离其他东西都很“远”。标准的空间树在这里会失效（需要近似算法）。

小结

在本章中，我们将看到计算机图形学、数据库和 GPS 系统如何解决“在哪里”的问题。我们将明白，组织空间与整理杂乱的衣柜惊人地相似：把东西放进盒子里，再把盒子放进更大的盒子里。

让我们从最简单的维度开始：时间（一维区间）。