GIS空间数据库（27）Hilbert曲线

与Z-排序类似，Hilbert曲线也是一种空间填充曲线，它利用一个线性序列来填充空间，其构造过程如图所示。

理想情况下，这种映射会带来更少的磁盘访问，但由于磁盘访问的次数依赖于很多因素，如磁盘页面容量、分割算法、插入顺序等，因此，对于不同的查询，其磁盘访问的次数会有很大的不同。通常，可将给定查询代表的子空间中每个网格点的散列单元平均数，来作为衡量磁盘访问效率的标准。

实验证明，Hi1bert曲线的方法比Z-排序好一些，因为它没有斜线。不过Hilbert曲线算法的计算量要比Z-排序复杂。

Hilbert曲线的算法如下（Faloutsos and Roseman，1989）：

（1）读入x和y坐标的n比特二进制表示。

（2）隔行扫描二进制比特到一个字符串。

（3）将字符串自左至右分成2比特长的串si，其中i=1，...，n

（4）规定每个2比特长的串的十进制值di，例如“00”等于0，“01”等于1，“10”等于3，“11”等于2。

（5）对于数组中每个数字j，如果j=0把后面数组中出现的所有1变成3，并把所有出现的3变成1。j=3把后面数组中出现的所有0变成2，并把所有出现的2变成0。

（6）将数组中每个值按步骤5转换成二进制表示（2比特长的串），自左至右连接所有的串，并计算其十进制值。