R木
R木は、階層的に入れ子になった相互に重なり合う最小外接矩形 (MBR) で空間を分割する。R木のRは矩形 (Rectangle) を意味する。
R木の各ノードのエントリ数は可変である(事前に定義された上限がある)。葉ノード以外の各エントリには2つのデータが格納される。1つは子ノードへの参照であり、もう1つはその子ノードの全エントリを囲む外接矩形のデータである。
挿入および削除のアルゴリズムはこれらの外接矩形を使い、近い要素が同じ葉ノードに属するようにする(特に、新たな要素を挿入する際に、どの最下層の外接矩形にも収まらない場合、最も拡大が小さくて済む外接矩形に対応した葉ノードに属するようにする)。葉ノードの各エントリには2つのデータが格納される。1つは実際のデータ要素への参照であり(参照ではなく、葉ノード内に直接データ要素が格納される場合もある)、もう1つはそのデータ要素を囲む外接矩形のデータである。