空间索引 · 从均匀网格到 geohash
B+ tree 索引一列数字，是因为数字有全序：任何一个区间在索引里都是连续的一段。二维坐标没有这样的全序。把点按 排好，「 在 100 到 160 之间」确实能二分定位，可 那一维只能逐个过筛——512 见方的场上撒 2000 个点，60 见方的查询窗平均命中 27.25 个， 带里却躺着 234.13 个候选，8.59 倍的读放大全花在扔掉上。spatial index 要补的正是这一维。
本系列走四个结构加一条旁路。uniform grid 把平面等分成格子，定位是一次除法，代价是格子边长必须与查询半径匹配——实测 的平均查询半径 12.89，最省的格子边长恰好是 16。quadtree 改成按密度自适应细分，团簇分布下点级判定从 78.85 降到 21.70。k-d tree 轮流按维度切，最近邻查询「先走近侧、再用当前最优半径决定要不要回溯」这一步在 2 维只访问 0.74% 的节点，到 16 维升到 99.77%——维度灾难在这里是一条能画出来的曲线。R-tree 索引的是矩形而非点，插入选面积增量最小的孩子、分裂让两个新 MBR 重叠尽量小，把 Guttman 的二次分裂换成按次序对半切，同层兄弟重叠面积从 51.9 万涨到 800.8 万。
最后一条旁路不建树：把 与 的二进制位交错成一个整数（Morton code），空间邻近性被部分保留，于是可以塞进任何一维有序结构。geohash 是它的 base32 编码版本，前缀相同即区域相同——Redis 的 GEO 命令就是把 geohash 当 zset 的 score。代价写在一个反例里：本初子午线两侧相距 13.9 m 的两点，9 位 geohash 的公共前缀是 0，所以邻域查询必须查 9 个格。
起点：查询谱系与等分平面
空间查询有三类形状：矩形范围（range）、最近邻（kNN）、对象相交。三类都要求索引保留邻近性，而把二维投影到一维必然丢掉一个方向的邻近性。最朴素的补法是把平面等分成格子——定位 、实现二十行，但分布一倾斜就同时出现空桶与热桶。
一维索引答不了的问题
排序索引依赖全序，而二维坐标没有全序。把点按 x 排好之后，「矩形里有哪些点」只能靠 x 带筛出候选再逐个过滤，512 见方场上 60 见方的窗口平均读放大 8.59 倍；最近邻查询连候选集都圈不出来。
均匀网格与空间哈希
把平面等分成格子，点按格子号入桶，查询只看覆盖到的格子。定位是一次除法，实现二十行。代价是格子边长必须与查询尺度匹配，且分布一倾斜就同时出现空桶与热桶。
两个记账指标会给出相反的排名
空间查询与网格 · 延伸阅读
- Spatial database — Wikipedia en.wikipedia.org 总览：空间查询的类型、常见索引结构，以及 PostGIS 与 Oracle Spatial 的实现选择。
- Spatial hashing for collision detection gamedeveloper.com 游戏里最常见的空间哈希写法：格子号直接当哈希 key，不建显式网格数组，稀疏场景省内存。
- PostGIS · Spatial Indexing postgis.net GiST 索引在 PostGIS 里怎么用，以及为什么空间查询要分成 index scan 加 recheck 两步。
自适应：按数据切，而不是按坐标切
均匀网格的格线位置由坐标系决定，与数据无关。两种改法：quadtree 保留「四等分」的规则形状但按点密度决定切到多深；k-d tree 干脆让格线穿过数据的中位数，于是每次切分都把点数对半分。前者的形状可预测、易并发，后者的树高有保证、但静态。
quadtree 与 octree
格线仍落在区域正中，但切多深由局部点密度决定。容量阈值与深度上限共同封住递归；坐标完全重合的点会把树抽成一条链，64 个同坐标点在深度上限 12 下造出 49 个节点。
k-d tree 与最近邻回溯
每层按一个维度切，切分面穿过 median，于是树高恒为 log n。最近邻查询「先走近侧、再用当前最优半径判断要不要回溯」这一步在 2 维只访问 0.74% 的节点，到 16 维升到 99.77%。
容量阈值不是越小越好
quadtree 与 k-d tree · 延伸阅读
- Finkel & Bentley · Quad Trees: A Data Structure for Retrieval on Composite Keys (1974) link.springer.com quadtree 的原始论文，提出按坐标四分递归划分平面的检索结构。
- Bentley · Multidimensional Binary Search Trees Used for Associative Searching (1975) dl.acm.org k-d tree 的原始论文：逐层轮换切分维、范围查询与最近邻的分析。
- Friedman, Bentley & Finkel · An Algorithm for Finding Best Matches in Logarithmic Expected Time (1977) dl.acm.org 最近邻查询的回溯剪枝算法与期望复杂度分析，本系列 k-d tree 页 kNN 的写法出处。
- Hanan Samet · 空间数据结构主页 cs.umd.edu quadtree 与空间索引领域两本标准教材的作者页，含大量讲义与实现笔记。
扩展：矩形对象与一维化
被索引的东西常常不是点，而是有形状的对象——地块、包围盒、时间区间。R-tree 让节点存孩子的最小外接矩形，于是同一套「剪掉不相交的子树」的逻辑照样成立，代价是兄弟 MBR 可以重叠、一次查询可能同时下几条分支。另一条路彻底放弃树：把二维坐标交错成一维整数，让现成的 B+ tree 或 zset 干活。
geohash 的前缀性质在格子边界处失效
gcpuzzrcj 与 u10hbp214，公共前缀长度为 0。
成因是二分：每一位记录的是「在当前区间的哪一半」，落在分界线两侧的点从第一位起就分道扬镳，而分界线在每一层都存在。工程上的处理是查 9 个格——目标格加八邻域，Redis 的 GEOSEARCH 正是这么做的。R-tree 与一维化 · 延伸阅读
- Guttman · R-Trees: A Dynamic Index Structure for Spatial Searching (1984) dl.acm.org R-tree 的原始论文：MBR、ChooseLeaf 的面积增量准则、线性与二次分裂算法。
- Beckmann, Kriegel, Schneider & Seeger · The R*-tree (1990) dl.acm.org R-tree 的改良：把「重叠面积」与「周长」也纳入分裂与选枝判据，并引入强制重插。
Z-order 与 geohash
- Z-order curve — Wikipedia en.wikipedia.org 位交错的定义、与四叉树的对应关系，以及范围查询时怎么跳过 Morton 区间里的无关段。
- geohash.org geohash.org Gustavo Niemeyer 2008 年提出的原始服务，可直接对照本系列引擎的编码结果。
-
Redis · GEOADD
redis.io
Redis GEO 的实现说明：52 位 geohash 整数当 zset 的 score，
GEOSEARCH查九格再精算距离。 - Hilbert curve — Wikipedia en.wikipedia.org Hilbert 曲线的局部性优于 Z 曲线（相邻编码恒为相邻格），代价是编解码要逐位旋转坐标。
收束：同一批查询下的横向对照
四个结构在同一点集、同一批查询下的访问次数放在一起看，会发现「访问节点数」与「点级判定次数」给出的排名是反的。选型的判据不是渐近复杂度——它们都是同一量级——而是数据是否动态、对象是点还是矩形、以及索引在内存还是在磁盘。
工程实现 · 延伸阅读
- rbush · JavaScript R-tree github.com Vladimir Agafonkin 的 R-tree 实现，采用 OMT 批量装载与 R*-tree 的重插策略，是前端做矩形相交检索的默认选择。
- kdbush · 静态点集的 k-d tree github.com 为「建一次查很多次」优化的实现：扁平 typed array 存树，无对象分配。
- S2 Geometry github.com Google 的球面索引库：把球面按 Hilbert 曲线映到 64 位 cell id，避开了经纬度矩形在两极的畸变。
- H3 · 六边形分层索引 h3geo.org Uber 的六边形网格：邻居距离一致（正方形网格的对角邻居远 41%），代价是层级之间不能整齐嵌套。