用四叉树和希尔伯特曲线做空间索引..doc

超酷算法：用四叉树和希尔伯特曲线做空间索引 阅读?·?四叉树,?希尔伯特曲线,?空间索引,?算法 Avalon探索之旅基础教程---- 简单绑定 Gopher China 2015 上海大会 Android必学-异步加载 Android必学-BaseAdapter的使用与优化 本文由?伯乐在线?-?demoZ?翻译，黄利民?校稿。未经许可，禁止转载！英文出处：。欢迎加入翻译组。 随着越来越多的数据和应用和地理空间相关，空间索引变得愈加重要。然而，有效地查询地理空间数据是相当大的挑战，因为数据是二维的（有时候更高），不能用标准的索引技术来查询位置。空间索引通过各种各样的技术来解决这个问题。在这篇博文中，我将介绍几种：四叉树，geohash（不要和geohashing混淆）以及空间填充曲线，并揭示它们是怎样相互关联的。 四叉树 四叉树是种很直接的空间索引技术。在四叉树中，每个节点表示覆盖了部分进行索引的空间的边界框，根节点覆盖了整个区域。每个节点要么是叶节点，有包含一个或多个索引点的列表，没有孩子。要么是内部节点，有四个孩子，每个孩子对应将区域沿两根轴对半分得到的四个象限中的一个，四叉树也因此得名。 图1??? 展示四叉树是怎样划分索引区域的 来源：维基百科 将数据插入四叉树很简单：从根节点开始，判断你的数据点属于哪个象限。递归到相应的节点，重复步骤，直到到达叶节点，然后将该点加入节点的索引点列表中。如果列表中的元素个数超出了预设的最大数目，则将节点分裂，将其中的索引点移动到相应的子节点中去。 图2??? 四叉树的内部结构 查询四叉树时从根节点开始，检查每个子节点看是否与查询的区域相交。如果是，则递归进入该子节点。当到达叶节点时，检查点列表中的每一个项看是否与查询区域相交，如果是则返回此项。 注意四叉树是非常规则的，事实上它是一种字典树，因为树节点的值不依赖于插入的数据。因此我们可以用直接的方式给节点编号：用二进制给每个象限编号（左上是00，右上是10等等译者注：第一个比特位为0表示在左半平面，为1在右半平面。第二个比特位为0表示在上半平面，为1在下半平面），任一节点的编号是由从根开始，它的各祖先的象限号码串接而成的。在这个编号系统中，图2中右下角节点的编号是1101。 如果我们定义了树的最大深度，不需通过树就可以计算数据点所在节点的编号：只要把节点的坐标标准化到适当的整数区间中（比如32位整数），然后把转化后x, y坐标的比特位交错组合。每对比特指定了假想的四叉树中的一个象限。（译者注：不了解的读者可看看Z-order，它和下文的希尔伯特曲线都是将二维的点映射到一维的方法） Geohash 上述编号系统可能看起来有些熟悉，没错，就是geohash！此刻，你可以把四叉树扔掉了。节点编号，或者说geohash，包含了对于节点在树中位置我们需要的全部信息。全高树中的每个叶节点是个完整的geohash，每个内部节点代表从它最小的叶节点到最大的叶节点的区间。因此，通过查询所需的节点覆盖的数值区间中的一切（在geohash上索引），你可以有效地定位任意内部节点下的所有数据点。 一旦我们丢掉了四叉树，查询就变得复杂一点了。我们需要事先构建有哪些信誉好的足球投注网站集合而不是在树中递归地精炼有哪些信誉好的足球投注网站集合。首先，找到完全覆盖查询区域的最小前缀（或者说四叉树节点??译者注：注意在我们的编号系统中节点由比特串表示）。在最坏情况下，这可能远大于实际的查询区域，比如对于在索引区域中心、和四个象限都相交的小块地方，查询将要从根节点开始。 现在的目标是构建一组完全包含查询区域的前缀，并且尽可能少包含区域外的部分。如果没有其他约束，我们可以简单地选择与查询区域相交的叶节点，但这会造成大量的查询。所以要加一个约束：使得要查询的不同区间最少。 一种达到这个目的的方法是先设置我们愿意承受的查询区间的最大数目。构建一组区间，最开始都设为我们之前指定的前缀。从中选择可以再分裂而不超出最大区间数并将从查询区域删除最不受欢迎区域的节点。重复这个过程直到集合中再没有区间可以细分。最后，检查得到的集合，如果可能的话合并相邻的区间。下面的图说明了这对于查询一个圆形区域且限制最大5个查询区间是如何工作的。 图3??? 一个对区域的查询是怎样分解成一连串geohash前缀/区间的 这个方法工作地很好，它使我们避免了递归查找。我们执行的一整套区间查找都可以并行完成。由于每次查找都预期要一次硬盘有哪些信誉好的足球投注网站，将查询并行化大大减少了返回结果需要的时间。 然而，我们还可以做得更好。你可能注意到上图中我们要查询的所有区域都是相邻的，但我们却只能将其中两个合并（选择区域的右下角的两个）成一个单独的查询，进而只要4次单独查询。（译者注：这两个区域可以合并是因为它们在geohash以Z字形遍历区域的路径上是相邻的）这