R 樹 (R-Tree)

Published: Wed Feb 18 2026 | Modified: Wed Feb 18 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