R*ツリーとは？空間データ索引のためのデータ構造を徹底解説

R*ツリーの基本概念

データ処理の分野において、R*ツリー（R*-tree）は、空間情報の索引付け（インデクシング）を実現するために実装された、Rツリーの派生形として定義されるデータ構造です。

データの再挿入（リインサート）が必要になる場合があるため、R*ツリーの構築コストは標準的なRツリーに比べてやや高くなります。しかし、その結果として得られるツリーは、一般的により優れたクエリ性能を発揮します。標準のRツリーと同様に、点データと空間データの両方を格納できる点も特長です。なお、R*ツリーの概念は1990年にノルベルト・ベックマン（Norbert Beckmann）、ハンス＝ペーター・クリーゲル（Hans-Peter Kriegel）、ラルフ・シュナイダー（Ralf Schneider）、ベルンハルト・ゼーガー（Bernhard Seeger）の4名によって提唱されました。

R*ツリーとRツリーの違い

R*ツリーは繰り返し挿入によって構築されます。この構造では領域間の重なり（オーバーラップ）がほとんど発生しないため、優れたクエリ性能が得られます。

Rツリーの性能にとって、カバレッジ（被覆面積）とオーバーラップの両方を最小化することは非常に重要です。オーバーラップが存在すると、データの挿入時や検索時に、複数の木の枝を展開する必要が生じます（データが互いに重なり合う領域に分割されているためです）。一方、カバレッジが最小化されていれば、枝刈り（プルーニング）の性能が向上し、特に否定条件を含む範囲検索において、ページ全体を検索対象から除外できる頻度が高まります。

R*ツリーはこの両方を削減することを目指しており、そのために改良されたノード分割アルゴリズムと、「ノード溢出時の強制再挿入（forced reinsertion）」という概念を実装しています。この考え方は、「Rツリーの構造はエントリの挿入順序に大きく左右されるため、一括ロードではなく挿入によって構築された構造は最適化されていない可能性が高い」という観察に基づいています。エントリを一度削除してから再挿入することで、現在の位置よりも適切な場所を木の中で「見つけ直す」ことが可能になります。

アルゴリズムと計算量

• 検索および削除操作については、R*ツリーは通常のRツリーと同様のアルゴリズムを採用しています。
• 挿入時には複合戦略を用います。葉ノードに対してはオーバーラップを最小化し、内部ノードに対しては拡大量と面積を最小化します。
• 分割時には、周囲長（ペリメーター）に基づいて分割軸を選択した後、オーバーラップを最小化する位相的分割（トポロジカル分割）を行います。
• さらに、強化された分割戦略に加えて、Bツリーのバランシングの概念に着想を得た手法として、オブジェクトや部分木を木に再挿入することで分割自体を回避しようとします。

したがって、最悪ケースにおける検索および削除の計算量はRツリーと同等です。挿入戦略に関しては、R*ツリーは O(M log M) の計算量を要し、Rツリーの線形分割戦略（O(M)）よりは複雑ですが、ページあたり M 個のオブジェクトを格納する場合の二次分割戦略（O(M²)）よりは単純であり、全体的な計算量への影響はわずかです。再挿入は木の中で最大でも1つの枝にしか影響せず、再挿入回数は O(log n) に収まるため、通常のRツリーで分割を行う場合と同等のコストにとどまります。結果として、挿入全体の計算量もRツリーと比肩しうる水準に維持され、総合的に見てR*ツリーの計算量は通常のRツリーと同等と言えます。