R木
オブジェクトを挿入するには、木を根ノードから再帰的に走査する必要がある。その時点の内部ノード配下の全ての矩形を調べる。新たなオブジェクトを含めるのに拡大が最小で済む矩形を選択する。この選択基準に適合する矩形が複数存在する場合、元々の領域が小さい方を選択する。この選択を再帰的に繰り返していく。葉ノードに到達したら、葉ノードに空きエントリがあれば、そのまま挿入すればよい。葉ノードに空きがない場合、挿入する前にノードの分割を行う。R木でのノード分割アルゴリズムはいくつか存在する。
同様に、探索アルゴリズム(例えば、共通部分、包含、最近傍)は外接矩形を使い、子ノードに対応する外接矩形内を探索すべきかどうかを判断する。このようにすると、探索においてほとんどのノードを走査する必要がなくなる。B木と同様、R木もデータベースに適しており、必要なノードだけをメモリ上にロードして操作することができる。
ノードが一杯になったときのノード分割アルゴリズムはいくつかあり、その方式によってR木は2次R木と線形R木に分けられる。
R木はこれまで最悪実行時間を保証できないとされてきたが、実世界のデータでは一般によい性能を発揮する。しかし2004年にPR木(Priority R木)という新たなアルゴリズムが発表された。これは、従来のものと同程度に効率的であると同時に、最悪時の性能も最適化されている。
R木(英: R-tree)は、B木に似た木構造のデータ構造であり、多次元情報(例えば、二次元座標データなど)のインデックス付け、すなわち空間インデックスに使われる。それは例えば、「現在位置から2km以内の全ての美術館を探す」といった用途に使われる。