Quad-tree 是什么？

顾名思义，四叉树（Quad-tree）就是不断的四等分空间矩形，如此递归下去，直至树的层次达到一定深度或者满足某种要求后停止分割。四叉树的结构比较简单，并且当空间数据对象分布比较均匀时，具有比较高的空间数据插入和查询效率，因此四叉树是常用的空间索引之一。

Quad-tree 例子

Why Quad-tree？

我认为它可以使得叶子节点上的数据量负载均衡，试想一下，如果是用传统的一个 Spatial Partition 的话，可能就会导致地图被分割的时候数据倾斜。举个简单的例子，比如我们去 partition 北京的地图，会发现内环的数据量特别大，的但是郊区的数据量小很多，这样就会造成后续的 workload 有很多负载不均导致的问题。

当然，它只是用一个非常简单的z思想去使得叶子节点的数据量“尽可能”均衡，但是一切都局限于它的一些超参。比如分裂的最大深度和每个叶子节点的最大数据量，满足这些个超参的话，该 Quad-tree 就会停止分裂。

怎么构建 Quad-tree？

Quad-tree 的论文

特别地，Quad-tree 是由... 提出，后续填坑。

Reference

1. 四叉树空间索引原理及其实现