幾何與區間：空間的架構

維度的詛咒

給數字排序很容易。5 比 3 大嗎？是的。 但給空間排序很難。(5, 3) 比 (4, 8) 大嗎？這取決於妳怎麼看。

當數據擁有多個維度（經度/緯度、開始時間/結束時間、X/Y/Z）時，簡單的列表就不夠用了。如果妳想找到「最近的加油站」或者「所有與下午 2 點重疊的會議」，妳不能簡單地掃描一個有序陣列。

本章的主題是 空間索引 (Spatial Indexing)。這是一門將空間（和時間）劃分為可管理層級的藝術，讓我們能以有限的速度查詢無限的平面。

分區的策略

在本章中，我們將從一維的線邁向 N 維的世界：

空間的三大法則

1. 層級 (Hierarchy)： 為了高效搜尋空間，妳必須將空曠的區域聚合在一起。如果一個大盒子是空的，妳就沒必要往裡看。
2. 重疊 (Overlap)： 與數字排序不同，空間物體可以重疊。一個健壯的演算法必須能處理「同時處於兩個地方」的模糊性。
3. 詛咒 (The Curse)： 隨著維度增加，距離變得毫無意義。在 1000 維空間中，任何東西離其他東西都很「遠」。標準的空間樹在這裡會失效（需要近似演算法）。

小結

在本章中，我們將看到電腦圖形學、資料庫和 GPS 系統如何解決「在哪裡」的問題。我們將明白，組織空間與整理雜亂的衣櫃驚人地相似：把東西放進盒子裡，再把盒子放進更大的盒子裡。

讓我們從最簡單的維度開始：時間（一維區間）。