2つの寸法を使用する場合、RツリーはZオーダーを維持できますか？

Question

Guttmanのオリジナルペーパーに基づいてR-Treeの実装を書いています。私は、マウスで移動/再サイズを移動できる/サイズを変更できる多くの長方形を含む、私が書いているプログラムにRツリーを使用することを考えていました。

特定の長方形にある長方形のみを効率的に選択して、それらを描画したい（潜在的に100以上のアイテムを反復し、境界が交差するかどうかを確認するのではなく）。 Guttmanの論文をいくつか読んだ後に私が見つけた問題は、2DオブジェクトのZオーダーを維持できないということです。

たとえば、オブジェクトを移動すると、削除されてから再挿入されます。再挿入されると、挿入されたノードは適切な順序を追跡できません。私が見たR-Treeのほとんどの実装は、配列を使用し、空の位置を見つけるだけです。再挿入は、本質的にZオーダーの位置を破壊します。

したがって、長方形と交差するすべての長方形を描くために行くとき、それらが返される順序は必ずしも正しいとは限りません。

私はこの仮定について間違っていますか？配列を使用する代わりに、AVLまたは赤黒の木を使用して使用できると考えていました。 Comparer これは、ツリーに挿入するz-indexを比較します。このようにして、Zオーダーは常に維持されます（そして、それは最も重要な要素です）。

また、戻ってきたときに並べ替えることを考えていましたが、これはもっと高価になる可能性があります。

Answer 1

R-Treeは、どういうわけか回答レコードを注文することは想定されていません。

答えを並べ替えてください。遅すぎません。

ところで、R-Treeコードを郵送できます。私にとってはうまくいきますが、誰かがガットマンやベックマンが彼らの論文で書いたものをチェックするなら、それは非常に便利です...

空間インデックスの順序は、厳密な順序とは本質的に異なります...空間インデックス作成とB+ツリーのみの違いです。

また、2つのインデックスを使用して参加することもできます。あなたは本当にあなたがインデックスが必要なのは本当にシュアですか？何かが遅くなりますか？