5

R* Tree を永続的な (ディスクベースの) ものとして実装するにはどうすればよいですか? R* ツリー インデックスまたはリーフ値を保存するためのファイルのアーキテクチャは何ですか?

注: さらに、そのような永続的な R* ツリーで挿入、更新、および削除操作を実行するにはどうすればよいですか?

メモ II: バルク ロード機能を備えたインメモリ R ツリーを実装しました。しかし、ディスクベースのものについて話すとき、それはまったく無関係だと思います.

4

3 に答える 3

8

ファイルのアーキテクチャ

さて、それはページ（=ブロック）です。ページは、基盤となるストレージのページサイズの倍数である必要があるため、おそらく1kbまたは8kbのブロックです。各ブロックには番号があり、この方法で参照できます。

ディレクトリページには、子のバウンディングボックスとそのページ番号が格納されます。

子ページには、実際のデータオブジェクトが格納されます。

ツリーの管理

理論的には、メモリ内のページを変更するたびに、変更内容をディスクに書き込みます。それでおしまい。

実際には、パフォーマンスのためにキャッシュを使用したり、アプリケーションがクラッシュした場合にツリーの一貫性を維持するためのトランザクションを使用したりすることができます。

これらの両方について、RDBMSアーキテクチャの分野で多くの文献を見つけることができます。

R *ツリーの主な利点は、あらゆる場所のデータベースシステムに存在するのと同じように、通常のページ指向のツリーであるということです。ディスク上のB+ツリーの実装に優れている場合は、コードのほとんどをR*ツリーに再利用できます。

どうやって始めるのか

開始するには、従来のRDBMSで行われているように、ディスクベースのデータインデックス作成に慣れる必要があります。ディスク上のBツリーまたはB+ツリーから始めることをお勧めします。削除されたページなどの管理について考える必要があるため、削除を許可してください。

ディスク上のBツリーを理解したら（そしておそらくそれを最適化するのに少し時間を費やす！）、ディスク上のRツリーを実行することはかなり明白なはずです。

私はコードを見たことがありませんが、これは良い出発点かもしれません：http ://www.die-schoens.de/prg/またはC++でのディスクベースのB+ツリー実装の検索でリンクされている他のいくつかまたはC

于 2012-12-02T10:59:46.320 に答える
4

ディスク上の R-Tree インデックスが必要な場合は、SpatialiteまたはPostgisを使用することをお勧めします。Spatialite は軽量で、スタンドアロン アプリケーションに簡単に組み込むことができます。または、 C# Spatial Index プロジェクトを見ましたか? . 私は数年前に Java で R ツリーの実装を作成しましたが、既に何かが存在する場合はお勧めしません。

于 2012-11-28T14:21:46.173 に答える
2

すでにメインメモリの実装がある場合は、同じコードを再利用して、ディスクに書き込みを追加するだけです。ページサイズを考慮し、ツリーノードを最適化してページに収まるようにする必要があります（一度に読み取ることができます）。

すべての変更をディスクに書き込むよりも、メインメモリツリーのスナップショットをディスクに保存しておく方が（パフォーマンスの面で）優れています（ツリーに高圧がかかっていないときにスナップショットを撮ることができます）。

質問では、ツリーのクエリの重要性が高いことを指定します。したがって、R *ツリーを使用すると、ツリーノード間のオーバーラップが最小限に抑えられるため、より適切になります。ただし、要件が更新操作（挿入/削除）に焦点を当てている場合は、Rツリーでの頻繁な更新のサポート：ボトムアップアプローチペーパーを参照することをお勧めします。

于 2012-11-28T14:40:10.143 に答える