|
R木（）は、B木に似た木構造のデータ構造であり、多次元情報（例えば、二次元座標データなど）のインデックス付け、すなわち空間インデックスに使われる。それは例えば、「現在位置から2km以内の全ての美術館を探す」といった用途に使われる。 == 概要 == R木は、階層的に入れ子になった相互に重なり合う最小外接矩形 (MBR) で空間を分割する。R木のRは矩形 (Rectangle) を意味する。 R木の各ノードのエントリ数は可変である（事前に定義された上限がある）。葉ノード以外の各エントリには2つのデータが格納される。1つは子ノードへの参照であり、もう1つはその子ノードの全エントリを囲む外接矩形のデータである。 挿入および削除のアルゴリズムはこれらの外接矩形を使い、近い要素が同じ葉ノードに属するようにする（特に、新たな要素を挿入する際に、どの最下層の外接矩形にも収まらない場合、最も拡大が小さくて済む外接矩形に対応した葉ノードに属するようにする）。葉ノードの各エントリには2つのデータが格納される。1つは実際のデータ要素への参照であり（参照ではなく、葉ノード内に直接データ要素が格納される場合もある）、もう1つはそのデータ要素を囲む外接矩形のデータである。 同様に、探索アルゴリズム（例えば、共通部分、包含、最近傍）は外接矩形を使い、子ノードに対応する外接矩形内を探索すべきかどうかを判断する。このようにすると、探索においてほとんどのノードを走査する必要がなくなる。B木と同様、R木もデータベースに適しており、必要なノードだけをメモリ上にロードして操作することができる。 ノードが一杯になったときのノード分割アルゴリズムはいくつかあり、その方式によってR木は2次R木と線形R木に分けられる。 R木はこれまで最悪実行時間を保証できないとされてきたが、実世界のデータでは一般によい性能を発揮する。しかし2004年にPR木（Priority R木）という新たなアルゴリズムが発表された。これは、従来のものと同程度に効率的であると同時に、最悪時の性能も最適化されている。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「R木」の詳細全文を読む スポンサード リンク
|