本文翻译自 An interactive intro to quadtrees，原载于 Hacker News。

问题：当暴力搜索不够快时

假设你正在开发一个地图应用。数据库里有数百万个餐厅、加油站和地标，每个都有经纬度坐标。用户点击屏幕问：「我附近有什么？」

最简单的方法是检查每个点。计算用户位置到数据库中每个餐厅的距离，保留足够近的，扔掉其他的。

这方法可行，但很慢。

一千个点时，你几乎察觉不到延迟。一百万个点时，每次查询都要做一百万次距离计算。在手机上，地图随着用户滚动实时更新，这是无法接受的。

暴力搜索会逐个检查每个点，无论它在地图的哪个位置。地图另一端的点获得与查询区域旁边的点相同的待遇。我们做了大量不必要的工作。我们无法跳过明显太远的点。

如果我们能够组织空间本身，使得搜索时可以立即排除整个区域呢？

空间划分的艺术

想象你在一个大房间里找一把丢失的钥匙。你不会逐平方英寸地检查。你会把房间分成几个区域（沙发旁边、门附近、桌子下面），然后一眼排除整个区域。「我没去过厨房，跳过那里。」

四叉树（Quadtree） 对二维空间做的正是这件事。它取一个矩形区域，将其分成四个相等的象限：西北、东北、西南、东南。如果某个象限里的点太多，它会再次细分，一次又一次。每次细分都会创建更小的单元格，点密集的地方单元格更小。

树的构建过程如下：

1. 树开始时是覆盖整个空间的单个区域
2. 随着点的到来，它们被放入包含它们的区域
3. 当一个区域超过其容量（分裂前可容纳的最大点数），该区域分成四个子区域
4. 现有的点被重新分配到子区域中

点密集的区域会持续细分，点少或没有点的区域保持较大。树会适应数据：密集区域获得细粒度单元格，稀疏区域保持粗糙。 分裂网格是预先确定的（总是在中点），但树只细化需要它的单元格。

网格背后的树结构

可视化中的网格线代表底层的树结构。每个区域是一个节点。当节点分裂时，它创建四个子节点。根节点覆盖整个空间。叶节点（没有子节点的节点）保存实际的点。

空间视图（矩形的网格）和树视图（节点的层级）代表相同的结构。搜索一个点意味着沿树向下走：在每个节点，你检查四个子节点中哪一个包含你的目标坐标，然后递归进入该子节点。你永远不会访问其他三个。

这与二分查找的思想相同。在排序数组中，你与中间元素比较并消除一半的候选者。在四叉树中，你选择四个象限之一并忽略其他三个区域。每一层将搜索空间缩小四倍而不是两倍。

调整分裂参数

每个节点的容量（分裂前可容纳多少点）控制树的形状。

• 低容量意味着节点早分裂，产生深度树和许多小单元格
• 高容量意味着节点在分裂前容纳更多点，产生浅树和更大的单元格

这里有一个权衡：较低的容量意味着查询时可以跳过更多空间（更快地缩小范围），但树有更多节点，使用更多内存。较高的容量意味着更少的节点，但每个节点需要线性检查更多点。

作为起点，4 到 16 之间的容量是合理的默认值，尽管最佳值取决于你的数据分布和查询模式。

点查询：从根到叶

现在我们可以构建树，让我们用它来搜索。找到一个特定点意味着从根开始问：哪个子象限包含这个坐标？然后递归进入该子节点并再次询问。树的每一层将搜索空间减少约四分之三。

注意高亮区域如何在每一步缩小。算法从不检查缩小窗口外的点。

在有 n 个点的平衡树中，这大约需要 log₄(n) 步。对于一百万个点，大约是 10 步而不是一百万次比较。

范围查询：找到区域内的所有内容

点查找很有用，但你更常使用的操作是范围查询：给树一个矩形区域，检索其中的每个点，而不扫描整个数据集。

算法递归地遍历树。在每个节点，它检查：

1. 这个节点的边界框是否与查询矩形重叠？
2. 如果不重叠，整个子树被剪枝（跳过）
3. 如果重叠，它测试节点的点是否在查询范围内，并递归进入子节点

被剪枝的节点代表算法从未检查的整个空间区域。 这些区域内的点从未被检查。将「访问的节点」计数与总点数进行比较。四叉树比暴力扫描做的工作少得多。

效率取决于查询大小相对于数据分布：

• 稀疏区域的小查询几乎剪枝所有内容
• 覆盖整个空间的查询不剪枝任何内容（因为每个节点都重叠），退化为暴力扫描

四叉树在查询是空间局部时给你最大的好处，这正是地图应用、游戏物理和空间数据库的常见情况。

最近邻搜索：找到最近的点

范围查询问「这个盒子里有什么？」但有时问题是「什么离这个位置最近？」这是最近邻问题，你不知道搜索半径应该有多大。最近的点可能就在你旁边，也可能很远。

算法维护一个从无穷大开始的「最佳距离」。当它遍历树时，检查每个访问的点，如果找到更近的点就更新最佳距离。在递归进入子节点之前，它检查该子节点边界框中可能最近的点是否比当前最佳距离更远。如果是，整个子树被剪枝。

虚线圆圈显示当前最佳距离。随着算法找到更近的点，圆圈缩小，这导致更多子树无法通过「可能包含更近的点？」测试并被剪枝。搜索通常随着进行变得更便宜。

对于分布良好的点，最近邻搜索在实践中通常是 O(log n)。在最坏情况下（所有点紧密聚集或沿一条线），它可能退化为 O(n)，但这在典型的空间数据中不常见。

碰撞检测：游戏中的应用

游戏和物理模拟需要检测哪些物体正在接触或重叠。对于 n 个物体，检查每对是 O(n²) 比较，很快就会变得昂贵。一百个物体意味着大约 5,000 次配对检查。一千个意味着近 500,000 次。

四叉树减少了这个工作量：每帧重建树，对于每个物体，只查询附近区域。远象限中的物体永远不会被比较。

每帧重建树。对于这种规模的场景，四叉树构建足够快，可以从头重建，尽管更大的模拟可能受益于增量更新。每个粒子查询其邻域以查找潜在碰撞，通常只检查 5 到 15 个候选者而不是全部 40 个。

真正的游戏引擎使用这种模式（或其 3D 表亲 Octree）进行宽相碰撞检测：四叉树快速识别候选对，更昂贵的窄相检查测试实际几何。

图像压缩：不仅仅是点数据

四叉树不限于点数据。它们也可以分割连续数据的区域，如图像的像素。

你看图像的一个区域。如果所有像素大致相同颜色（低于某个阈值），你将整个区域的平均颜色存储为单个值。如果像素变化太大，你将区域分成四个象限并重试。

• 均匀区域（纯色背景、平滑渐变）存储为大块
• 细节区域（边缘、纹理）被细分成更小的块

你最终得到一个压缩表示，在存在细节的地方保留细节，在可以简化的地方简化。

基于四叉树的图像压缩格式和细节层次系统都这样工作。卫星图像、地形渲染和地理信息系统使用四叉树分解以不同分辨率提供数据：缩小时，你看到大的粗糙块；放大时，你看到细粒度图块。

真正的图像压缩（JPEG、PNG）使用不同的技术（DCT、熵编码），但四叉树捕获相同的原则：在细节所在的地方花费比特，而不是均匀地分布在整个图像上。

四叉树的实际应用

四叉树存在于空间数据存在的任何地方：

• 地图服务使用类似四叉树的图块金字塔以不同缩放级别提供地图图块（例如，Bing 的 quadkey 系统将图块寻址为四进制路径）
• 游戏引擎使用它们进行碰撞检测和可见性剔除
• 地理信息系统使用空间索引来存储和查询空间数据集
• PostGIS 使用 GiST 索引（R 树风格）对几何图形进行空间查询，而 PostgreSQL 的核心支持类似四叉树的 SP-GiST 索引用于某些数据类型如点

四叉树是更广泛的空间分区数据结构家族的二维情况：

每个变体在构建时间、查询速度和更新成本之间做出不同的权衡。

核心思想

它们都按位置组织数据，以便你可以跳过不相关的区域，将「检查所有内容」替换为「检查可能重要的事情」。

这就是让我们从一百万次比较减少到十次的原因。

原文包含大量交互式演示，强烈建议前往 原文网站 体验动态可视化效果，这对于理解四叉树的工作原理非常有帮助。