R 树 (R-Tree)

Published: Wed Feb 18 2026 | Modified: Sat Feb 07 2026 , 2 minutes reading.

R 树：装箱工

算法背后的故事：搬家箱子

想象你正在打包搬家。你有各种形状怪异的物品：一盏落地灯、一把吉他、一摞书。

你把书放进一个小箱子。
你把落地灯放进一个长箱子。
你把这两个箱子放进一个巨大的“客厅”箱子。

现在，有人问：“吉他拨片在哪里？” 你看着那些大箱子。“厨房箱？”不可能。“卧室箱？”不对。“客厅箱？”有可能。你打开“客厅”箱，检查里面的小箱子。

这就是 R 树 (Rectangle Tree)。与 K-D 树将空间切割成整齐、不重叠的区域不同，R 树将物体分组成 边界框 (Bounding Boxes)。这些盒子可以重叠，就像现实世界中的杂物一样。

为什么需要它？

R 树是 空间数据库（PostGIS, MySQL Spatial, Oracle Spatial）的行业标准。

“找出地图视图内的所有餐厅”： 地图视图是一个查询矩形。数据库找出所有与该矩形重叠的盒子。
“这个 GPS 点在哪条路上？”： 道路是复杂的多段线。R 树存储它们的边界框，以便快速过滤掉数英里之外的道路。

算法是如何“思考”的

这个算法是一个分层分组者。

MBR (最小边界矩形)： 每个物体（房子、道路）都被包裹在一个能装下它的最小矩形中。
叶子节点： 包含实际的物体。
内部节点： 包含指向子节点的指针，以及一个覆盖其子节点中所有矩形的大 MBR。
重叠： 与四叉树不同，R 树的子节点可以重叠。这使得插入变得复杂（你想最小化重叠），但使得查询非常灵活。

搜索逻辑：

从根节点开始。
根节点的盒子与我的查询框重叠吗？不重叠？剪掉它。
重叠？检查所有子节点。
重复直到到达叶子。

工程决策：分裂的头痛

R 树最难的部分是插入。当一个节点太满（例如 > 4 项）时，它必须分裂成两个节点。

二次分裂 (Quadratic Split)： 尝试每一对组合，看哪两颗“种子”能产生最小的新盒子。准确但慢。
线性分裂 (Linear Split)： 挑两个离得最远的项，然后把剩下的分给它们。快但会产生混乱的盒子。
R 树 (R-Star Tree)：* 生产环境中使用的优化版本。它试图最小化“重叠”而不仅仅是“面积”，有时会通过“重新插入”项来强制优化结构。

实现参考 (Python 素描版)

从头构建一个完整的 R 树代码量很大（分裂逻辑很繁琐）。这是搜索逻辑的概念素描。

class Rect:
    def __init__(self, x1, y1, x2, y2):
        self.x1, self.y1, self.x2, self.y2 = x1, y1, x2, y2
    
    def intersects(self, other):
        return not (self.x2 < other.x1 or self.x1 > other.x2 or
                    self.y2 < other.y1 or self.y1 > other.y2)

class Node:
    def __init__(self, is_leaf=False):
        self.is_leaf = is_leaf
        self.children = [] # 列表包含 (MBR, child_node_or_data)
        self.mbr = None    # 包含内部所有东西的大边界框

    def search(self, query_rect, results):
        # 1. 剪枝：如果我不碰到查询框，我里面的东西也不会碰到。
        if not self.mbr.intersects(query_rect):
            return

        # 2. 叶子检查
        if self.is_leaf:
            for mbr, data in self.children:
                if mbr.intersects(query_rect):
                    results.append(data)
            return

        # 3. 内部节点递归
        for mbr, child_node in self.children:
            # 在下降之前检查子节点的 MBR
            if mbr.intersects(query_rect):
                child_node.search(query_rect, results)

# 使用提示：
# 在 Python 生产环境中，请使用 'rtree' 库 (libspatialindex 的封装)。
# 除非为了学习，否则不要自己写 R 树！
# import rtree
# index = rtree.index.Index()
# index.insert(id=1, coordinates=(0,0,1,1))

小结

R 树教会我们：混乱的现实需要灵活的容器。通过允许边界流动和重叠，我们可以索引真实世界——连同它所有蜿蜒的道路和形状怪异的建筑——而不必将其强行塞入人造的网格中。它是算法的纯粹性与地理的混沌性之间的桥梁。

Luke Sun