資料庫必知詞彙：R-Tree

1984年，加州大學伯克利分校的Guttman發表了一篇題為“R-trees: a dynamic index structure for spatial searching”的論文，向世人介紹了R樹這種處理高維空間存儲問題的資料結構。R-Tree是B-Tree向多元空間發展的另一種形式，它将對象空間按範圍劃分，每個結點都對應一個區域和一個磁盤頁，非葉結點的磁盤頁中存儲其所有子結點的區域範圍，非葉結點的所有子結點的區域都落在它的區域範圍之内；葉結點的磁盤頁中存儲其區域範圍之内的所有空間對象的外接矩形。

R-Tree是一種空間索引資料結構，下面做簡要介紹：

（1）R-Tree是n 叉樹，n稱為R-Tree的扇（fan）。

（2）每個結點對應一個矩形。

（3）葉子結點上包含了小于等于n 的對象，其對應的矩為所有對象的外包矩形。

（4）非葉結點的矩形為所有子結點矩形的外包矩形。

R-Tree的定義很寬泛，同一套資料構造R-Tree，不同方可以得到差别很大的結構。什麼樣的結構比較優呢？有兩标準：

（1）位置上相鄰的結點盡量在樹中聚集為一個父結點。

（2）同一層中各兄弟結點相交部分比例盡量小。

R樹是一種動态索引結構。每個結點所能擁有的子結點數目有上、下限，下限保證對磁盤空間的有效利用，上限保證每個結點對應一個磁盤頁，當插入新的結點導緻某結點要求的空間大于一個磁盤頁時，該結點一分為二(分裂)。R樹是一種動态索引結構，即：它的查詢可與插入或删除同時進行，而且不需要定期地對樹結構進行重新組織。

R-樹是一種用于處理多元資料的資料結構，用來通路二維或者更高維區域對象組成的空間資料.R樹是一棵平衡樹。樹上有兩類結點：葉子結點和非葉子結點。每一個結點由若幹個索引項構成。對于葉子結點，索引項形如(Index，Obj_ID)。其中，Index表示包圍空間資料對象的最小外接矩形MBR，Obj_ID辨別一個空間資料對象。對于一個非葉子結點，它的索引項形如(Index，Child_Pointer)。 Child_Pointer 指向該結點的子結點。Index仍指一個矩形區域，該矩形區域包圍了子結點上所有索引項MBR的最小矩形區域。

R樹滿足的性質：

1. 除根結點之外，所有非根結點包含有m至M個記錄索引（條目）。根結點的記錄個數可以少于m。通常，m=M/2。
2. 對于所有葉子中存儲的記錄（條目），I是最小的可以在空間中完全覆寫這些記錄所代表的點的矩形（注意：此處所說的“矩形”是可以擴充到高維空間的）。
3. 對于所有非葉子結點上的記錄（條目），i是最小的可以在空間上完全覆寫這些條目所代表的點的矩形（同性質2）。
4. 所有葉子結點都位于同一層，是以R樹為平衡樹。

資料來源：

鄧紅豔, 武芳, 翟仁健, et al. 一種用于空間資料多尺度表達的R樹索引結構[J]. 計算機學報, 2016, 32(01).

肖予欽, 張巨, 景甯, et al. 基于R樹的方向關系查詢處理[J]. 軟體學報, 2004(01):106-114.

雷小鋒, 謝昆青, 韓亮, et al. 基于惰性聚類分裂的動态R樹實作方法[J]. 計算機科學, 2007, 34(4):102-103.

張明波, 陸鋒, 申排偉,等. R樹家族的演變和發展[J]. 計算機學報, 2005, 28(3):289-300.