KDBツリー

コンピュータサイエンスにおいて、KDBツリー（k次元Bツリー）は、 k次元の検索空間を細分化するためのツリーデータ構造です。KDBツリーの目的は、バランスのとれたkdツリーの検索効率を提供しながら、外部メモリアクセスを最適化するためにBツリーのブロック指向のストレージを提供することです。^[1]

k -d ツリーと同様に、KDB ツリーはk次元空間内のポイントを整理し、範囲検索や多次元データベース クエリなどのタスクに役立ちます。KDB ツリーは、単一のドメイン内の要素を比較することで、空間を 2 つのサブスペースに分割します。2-DB ツリー (2 次元 KDB ツリー) を例にとると、空間はk -d ツリーと同じ方法で分割されます。つまり、ドメイン (この場合は軸) の 1 つだけにあるポイントを使用すると、他のすべての値は現在の値より小さいか大きいかになり、それぞれ分割面の左側と右側になります。

k -d ツリーとは異なり、各ハーフスペースは独自のノードではありません。代わりに、B ツリーと同様に、KDB ツリーのノードはページとして保存され、ツリーはルート ページへのポインタを保存します。

KDB ツリーには 2 種類のページが含まれています。

• 領域ページ:境界領域の説明と、その領域に対応する子ページへのポインターを含む(領域、子)ペアのコレクション。
• ポイント ページ: (ポイント、場所)ペアのコレクション。データベースの場合、場所はデータベース レコードのインデックスを指す場合がありますが、k次元空間内のポイントの場合は、その空間内のポイントの座標として見ることができます。

ページ オーバーフローは、KDB ツリーに要素を挿入した結果、ノードのサイズが最適サイズを超えた場合に発生します。KDB ツリーの目的は、ハード ディスクからのアクセスなどの外部メモリ アクセスを最適化することであるため、ノードのサイズが外部メモリ ページ サイズを超えると、ページがオーバーフローしたか、またはオーバーフィルされたと見なされます。

挿入/削除操作全体を通じて、KDB ツリーは特定のプロパティ セットを維持します。

• グラフは多方向ツリーです。リージョン ページは常に子ページを指し、空にすることはできません。ポイント ページはツリーのリーフ ノードです。
• B ツリーと同様に、ツリーのリーフへのパスの長さはすべてのクエリに対して同じです。
• リージョン ページを構成するリージョンは分離されています。
• ルートがリージョン ページである場合、そのリージョンの結合が検索空間全体になります。
• リージョン ページ内の(リージョン、子)ペアの子もリージョン ページである場合、子内のすべてのリージョンの和集合はリージョンになります。
• 逆に、上記の場合、child がポイント ページである場合、child内のすべてのポイントは、 regionに含まれている必要があります。

KDB ツリー上のクエリは、ツリー内のすべてのドメインまたは軸の区間にわたる範囲検索です。この区間のコレクションは、クエリ領域と呼ばれます。k空間では、クエリ領域は、 k次元検索空間全体の一部のサブスペースの周囲の境界ボリュームとして視覚化できます。クエリは、次の 3 つのカテゴリのいずれかに分類されます。

• 一部の間隔はドメイン全体または軸全体にまたがり、クエリは部分範囲クエリになります。
• 一部の間隔はポイントであり、その他は完全なドメインであるため、クエリは部分一致クエリになります。
• 間隔はすべてポイントなので、境界ボリュームもポイントになります。これは完全一致クエリです。

1. ツリーのルートが null の場合は終了し、それ以外の場合はpage をルートにします。
2. ページがポイント ページの場合、クエリ領域内にある(ポイント、場所)ペアのすべてのポイントを返します。
3. それ以外の場合、ページはリージョン ページであるため、リージョンとクエリ リージョンが交差するすべての(リージョン、子)ペアに対して、ページを子に設定し、手順 2 から再帰します。

KDB ツリーへの挿入では、ページ オーバーフローが発生した場合にページの分割が必要になる可能性があるため、最初に分割操作を定義することが重要です。

まず、領域ページをある平面に沿って分割し、左ページと右ページの 2 つの新しい領域ページを作成します。これらのページには古い領域ページの領域が埋め込まれ、古い領域ページは削除されます。次に、元の領域ページ内のすべての ( region、child ) について、child はページであり、region は実際の境界領域を指定することを覚えておいてください。

1. 領域が分割面の左側に完全に存在する場合は、左ページに(領域、子)を追加します。
2. 領域が分割面の右側に完全に位置している場合は、右ページに(領域、子)を追加します。
3. さもないと：
   1. 分割平面によって子を再帰的に分割し、 new_left_pageとnew_right_page というページを作成します。
   2. 分割平面で領域を分割し、 left_regionとright_regionを作成します。
   3. 左ページに(left_region, new_left_page)を追加し、右ページに(right_region, new_right_page)を追加します。

分割アルゴリズムを使用すると、新しい(ポイント、場所)ペアの挿入は次のように実装できます。

1. ルートページがnullの場合は、ルートページを(ポイント、場所)を含む新しいポイントページにするだけです。
2. ポイントに完全一致するクエリを実行すると、そのポイントを追加するページが検索されます。ページ内に既に存在する場合は終了します。
3. ページに(ポイント、場所)を追加します。ページがオーバーフローする場合は、 page がそのページを表すようにします。
4. old_page をpageと等しくします。要素とドメイン/軸を選択して、page を分割する平面を定義します。これにより、2 つのページが作成されますが、新しいポイントの追加によってページの 1 つがいっぱいになることはありません。page を平面で分割して、2 つの新しいページnew_left_pageとnew_right_page、および 2 つの新しい領域left_regionとright_regionを作成します。
5. pageがルート ページの場合は、手順 6 に進みます。それ以外の場合は、 page がpageの親になります。 page 内の (region, old_page) を (left_region, new_left_page) および (right_region, new_right_page) に置き換えます。pageがオーバーフローした場合は手順4 を繰り返し、それ以外の場合は終了します。
6. left_region を分割平面の左側の検索空間全体とし、right_regionをステップ 4 の分割の結果としての右側の検索空間とします。ルート ページを、left_regionとright_region の領域を含むページに設定します。

ページを分割するために選択するドメインと要素には注意が必要です。分割面の両側のポイントの数のバランスを取ることが望ましいからです。場合によっては、分割ドメインの選択が適切でないと、望ましくない分割が行われることがあります。また、ページを特定のドメインで分割できない可能性もあります。

ストレージ使用率に最小要件が設定されていない場合、KDB ツリーからの削除は非常に簡単です。完全一致クエリを使用して(ポイント、場所)ペアを検索し、存在する場合はツリーからレコードを削除するだけです。

削除によってページに含まれるデータが非常に少なくなる可能性があるため、最低限のストレージ使用率の基準を満たすように KDB ツリーを再編成する必要がある場合があります。ページに含まれるデータが少なすぎる場合に使用される再編成アルゴリズムは次のとおりです。

1. page をPの親とし、(region, P)を含みます。
2. ページ内の領域が隣接しており、それらの結合によって長方形の領域が形成される領域を検索します。これらの領域は「結合可能」であると見なされます。Rはこれらの領域の集合を表します。
3. セットR を1 つのページSにマージし、Sがいっぱいの場合は、結果のページがいっぱいでなくなるまで繰り返し分割します。
4. ページ内の領域の集合R を、 S を分割して得られたページに置き換えます。

k -d ツリーと同様に、KDB ツリーの更新では、複数のノードを再帰的に分割する必要が生じる場合があります。これは非常に非効率的であり、多くのほぼ空の葉が生じる可能性があるため、メモリの使用率が最適ではない可能性があります。Lomet と Salzberg は、挿入後に発生する分割を 1 つのルートから葉へのパスのみに制限することで、KDB ツリーのパフォーマンスを向上させる hB ツリー (穴あきレンガ木) と呼ばれる構造を提案しました。これは、領域を長方形としてだけでなく、中心から長方形を取り除いた長方形として保存することで実現しました。^[2]

最近では、Bkdツリーが静的KDBツリーの高速クエリとほぼ100%のスペース利用率を提供する手段として提案されました。単一のツリーを維持して再バランスをとる代わりに、KDBツリーのセットが維持され、定期的に再構築されます。^[3]この場合、はポイント数で表されたメモリバッファのサイズです。 ${\displaystyle \log_{2}(N/M)}$${\displaystyle M}$