Joe Celko のネストされたセット (変更された事前注文トラバーサル) の既知の制限の中には、ツリーが大きなサイズに成長するにつれてパフォーマンスが著しく低下するというものがあります。
Vadim Tropashko はネストされた間隔を提案し、この論文で例と理論の説明を提供します: http://arxiv.org/html/cs.DB/0401014
これは実行可能なソリューションですか?ネイティブ DB レイヤーから抽象化された (任意の言語での) 実行可能な例はありますか?
質問する
5691 次
2 に答える
7
入れ子集合の例を見てきましたが、入れ子間隔の例はあまり見ていませんが、理論的には、一方から他方への変換は難しくないはずです。ノードにラベルを付けるために事前順序トラバーサルを実行する代わりに、幅優先再帰を実行します。秘訣は、ノードのn個の子にラベルを付ける最も効率的な方法を見つけることです。a/bとc/dの間のノードは（a + c）/（b + d）であるため、条件数の悪い挿入（たとえば、子を左から右に挿入）は、同じ指数関数的成長を生み出すリスクがあります。たとえば、完全なマテリアライズドパスを使用するなどのインデックス値で。この影響を打ち消すことは難しくありません。新しいインデックスを一度に1つずつ作成し、結果の分母が最も低くなる場所にそれぞれを挿入します。
パフォーマンスの低下に関する限り、実行する操作に大きく依存します。ツリー全体の完全な再ラベル付けを必要とする操作がまだいくつかあります。ネストされたセットまたはネストされた間隔のメソッドはどちらも、ほとんど変更されない構造に最適です。階層に対して多くの構造変更を行う場合は、「標準」の親子テーブル構造の方が扱いやすい場合があります。一部の操作（子孫の数など）は、区間メソッドよりもネストされたセットの整数ラベル付けの方がはるかに簡単であることも忘れないでください。
于 2008-12-12T21:32:48.087 に答える
1
いくつかのシステムの本番環境で使用されるRailsのActiveRecordhttps ://github.com/clyfe/acts_as_nested_interval/で使用される、ネストされた間隔のすべての計算を抽象化するgemを作成しました。
于 2012-09-25T23:36:06.663 に答える