Morton code · base32 前缀 · 九格

geohash 与 Z-order

前四个结构都在建树。还有一条路根本不建结构：把二维坐标编码成一个一维整数，然后交给现成的 B+ tree 或有序集合。

这条路的全部价值取决于一件事：编码能保留多少空间邻近性。完全保留是不可能的，二维到一维的连续双射不存在。能做到的是「大部分时候相近」，而剩下那部分「不相近」的处理方式，构成了这条路上全部的工程内容。

1 · 位交错

把 $x$ 与 $y$ 的二进制位一位一位交替排开，得到的整数叫 Morton code。

定义 1.1（Morton code） 设 $x = x_{n-1} \dots x_1 x_0$ 、 $y = y_{n-1} \dots y_1 y_0$ 为二进制，则 $Z(x, y) = y_{n-1} x_{n-1} \dots y_1 x_1 y_0 x_0$ 即 $x$ 占偶数位、 $y$ 占奇数位。按 $Z$ 值从小到大访问网格，走出的折线形如反复出现的 Z 字，故也称 Z-order curve。

$Z(3, 5)$ 的算法是： $x = 011$ 、 $y = 101$ ，交错得 $100111 = 39$ 。逆变换同样是纯位运算，抽掉插进去的那些 0 即可。实现里用的是经典的位并行做法（part1by1 与 compact1by1），把「每位之间插一个 0」拆成 4 次移位与掩码，不用循环。

图 1-1 · 位交错与 Z 曲线。上方是

x

与

y

的位如何穿插成一个整数，下方是 Z 曲线在网格上的走法。可改网格位数并拖动画布选点，也可框出一块区域看它对应的 Morton 区间。

与 quadtree 的对应关系值得记一笔：Morton code 的最高两位就是这个点在根节点的哪个象限，次两位是在下一层的哪个象限，依此类推。一个 $b$ 位 Morton code 的前 $2j$ 位，正好是它在深度 $j$ 的 quadtree 里的路径。 于是「同一个格子里的点共享 Morton 前缀」这条性质，与「同一个 quadtree 节点下的点共享路径」是同一句话。

2 · 局部性保留了多少

「部分保留」这个说法可以量化。

64 × 64 的网格上，取遍全部水平相邻的格子对，两者 Morton code 之差的均值是 21.67，其中 4.76% 的差超过 64（一整行的宽度）。最坏的一对是 $(31, 0)$ 与 $(32, 0)$ ，物理上紧挨着，Morton code 却差 683（全网格只有 4096 个位置）。小尺度上也一样： $Z(3,3) = 15$ 而 $Z(4,3) = 26$ ；反过来 $Z$ 值相邻的 15 与 16 对应的是 $(3,3)$ 与 $(4,0)$ ，纵向差了 3 格。

对范围查询的影响更直接。同一个 64 × 64 网格上取一块 16 × 16 的区域（256 个格子），它覆盖的 Morton 值最小 204、最大 963，一维区间长 760。也就是说，若直接把这个区间丢给 B+ tree 做一次 range scan，读回来的 760 个格子里有 504 个与查询区域无关，无关比例 66.32%。

这个数是这条路的真实代价。工程上的对策是把一个矩形分解成若干段互不相交的 Morton 区间，段数越多越精确、但发出的 range scan 也越多。实现这一步的算法叫 BIGMIN 或 litmax/bigmin，思路是找出区间里第一个「跳出查询矩形」的位置，从那里切开。

3 · geohash 的 base32 编码

geohash 是 Morton code 在经纬度上的字符串版本。

定义 3.1（geohash） 对经度区间 $[-180, 180]$ 与纬度区间 $[-90, 90]$ 交替二分，每次记录一位：落在上半为 1、下半为 0。首位取自经度。每攒够 5 位查一次 32 字符表，得到一个字符。字母表去掉了 a、i、l、o 四个易混字符，剩下 0 到 9 这十个数字与 22 个字母。

于是精度按字符数呈几何级数变化。北纬 39.9042、东经 116.4074 处：

字符数	geohash	格子尺寸（纬向 × 经向）
2	`wx`	626 km × 961 km
3	`wx4`	157 km × 120 km
4	`wx4g`	19.6 km × 30.0 km
5	`wx4g0`	4.89 km × 3.75 km
6	`wx4g0b`	611 m × 938 m
7	`wx4g0bm`	153 m × 117 m
8	`wx4g0bm6`	19 m × 29 m

每加一个字符面积缩小 32 倍，长宽交替缩小 8 倍与 4 倍：5 位一个字符，奇偶字符分给两个维度的位数不同（3 : 2 与 2 : 3 交替）。这也解释了为什么格子在奇数长度时偏扁、偶数长度时偏方。

前缀性质由此成立：两个 geohash 的公共前缀越长，它们所在的格子越小、也就越接近。这条性质让 geohash 能塞进任何一个支持前缀匹配或范围扫描的一维索引。

图 3-1 · geohash 的逐字符细分与九格邻域。画布是等距圆柱投影的经纬度平面，蓝框是当前格、周围八格用虚线标出。可拖动选点、改精度，读数给出编码、格子尺寸与八邻域。

4 · 边界处的前缀断裂

前缀性质的逆命题不成立：位置接近的两个点，前缀可以完全不同。

伦敦本初子午线两侧、纬度同为 51.5 的两点，经度分别是 $-0.0001$ 与 $+0.0001$ ，实际相距 13.9 m。9 位 geohash 分别是 gcpuzzrcj 与 u10hbp214，公共前缀长度为 0。

成因是二分本身。每一位记录的是「在当前区间的哪一半」，落在分界线两侧的点从该位起就分道扬镳；而分界线在每一层都存在，最粗的那条正是本初子午线与赤道。任意精度的格子边界上都有这么一对点。

警示 · 「按前缀查邻居」的写法在格子边界上会漏掉一半结果，而且漏得毫无规律——查询点落在格子中央时一个不漏，贴着边界时漏掉整整一侧。这种「大部分情况正确」的缺陷在测试里最难暴露，随机采样的查询点几乎都落在格子中央。

工程上的处理是查九个格：目标格加上它的八邻域。上面那对点在 5 位精度下分属 gcpuz 与 u10hb，而 gcpuz 的八邻域正是 gcpvp、u10j0、u10hb、u10h8、gcpux、gcpuw、gcpuy、gcpvn，u10hb 就在其中。九个格覆盖的范围至少是一个边长为格子边长的圆，所以只要查询半径不超过格子边长，九格就够。

求八邻域有两种写法。经典做法是查一张按方向与奇偶位置组织的 base32 转移表，逐字符进位。本系列的实现走另一条：解码出格子中心与格子尺寸，把中心朝八个方向各挪一个格子宽度，再按同样精度重新编码。这个写法短得多，代价是在两极附近会失真（纬度被钳在 $\pm 90$ ，北极点的「北邻」退化成自己），而转移表法在那里同样有特殊情形要处理。

5 · Redis GEO 的做法

Redis 没有专门的地理数据结构。GEOADD 把经纬度编码成一个 52 位的 geohash 整数，当作 sorted set 的 score 存进去；GEOSEARCH 按查询半径反推需要的精度、算出九个格、对每个格做一次 ZRANGEBYSCORE，把候选取出来后再逐个算真实的球面距离过滤。

这套做法的每一步都能对上前面的正文：整数形式就是不做 base32 编码的 Morton code；「按半径反推精度」就是 §2 的「格子边长与查询半径匹配」；「九个格」是 §4 的边界修补；最后那次精确距离过滤，则是因为 §2 量到的那个无关比例——一维扫回来的东西必然多于所需。

代价也清楚：一次 GEOSEARCH 是九次有序集合范围扫描加一轮距离计算，而不是一次树遍历。换来的是不需要任何新的存储结构，且天然支持持久化、复制与集群分片，因为 sorted set 已经有这一切。

6 · Hilbert 曲线

Z 曲线的局部性可以改进。Hilbert 曲线的相邻编码恒对应相邻格子（不存在 §2 里那种「差 64」的跳跃），因而同样长度的一维区间覆盖的空间更紧凑。

代价在编码。Morton code 是纯粹的位交错，四次移位掩码搞定；Hilbert 编码要逐层根据当前朝向旋转与翻转坐标，是一个带状态的循环，慢一个量级左右，且没有同样漂亮的位并行写法。

选哪个取决于查询与编码的比例。Google 的 S2 选了 Hilbert，因为它索引的是相对静态的地理数据、查询远多于写入；游戏引擎里的 Morton code 常用于每帧重排的粒子或体素，编码成本直接进热路径，Z 曲线的简单性更值钱。

7 · 参考文献

Morton, G. M. (1966). A computer oriented geodetic data base and a new technique in file sequencing. IBM Technical Report, Ottawa.
Orenstein, J. A., & Merrett, T. H. (1984). A class of data structures for associative searching. Proceedings of the 3rd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, 181–190.
Tropf, H., & Herzog, H. (1981). Multidimensional range search in dynamically balanced trees. Angewandte Informatik, 2, 71–77.
Moon, B., Jagadish, H. V., Faloutsos, C., & Saltz, J. H. (2001). Analysis of the clustering properties of the Hilbert space-filling curve. IEEE Transactions on Knowledge and Data Engineering, 13(1), 124–141.