2

私は PostgreSQL を使用しているので、 ltreeと呼ばれるモジュールがあります。これは、私のニーズの少なくとも 1 つ、パフォーマンスを満たします (スケーラビリティについてはわかりませんか?具体化されたパス ツリーはうまくスケーリングしないと誰かが言います..)。

私が開発しているアプリケーションは完全に大きなツリー、ノード、サブツリーなどを中心に構築された CMS であるため、これらのノードをキューに入れる際のパフォーマンスは絶対に不可欠ですが、階層的な大きな (成長するにつれて) ツリーであるため、作業し、そこから操作します。 GUI (CRUD)、データベース内のツリー (子レコード) を正しく更新しながら、ユーザーがドラッグ アンド ドロップしてノード、サブツリーなどを並べ替えられるようにしたいと考えています。

ツリー内のノード/サブツリーの移動と並べ替えは、実際には ltree/マテリアライズド パス ツリーの目的ではないことを理解しています。パフォーマンスとサブツリーとノードの移動、またはおそらく... ltreeが実際に過去からの残り物ではなく、まだ使用する価値がある場合、PostgreSQLのltreeモジュールでこれをどのように達成できますか? この場合、なぜ/なぜ ltree を使用しないのですか?

要件：

  1. もちろん、クエリのパフォーマンスは私の最優先事項です (すべてのノード、サブツリー、リーフ)。
  2. ツリーは、深いレベルのネストとソートをサポートする必要があります
  3. そしてもちろん、ツリーは大規模な成長とスケーリングをサポートする必要があります
  4. 1 つの「なんでも屋」ツリーの実装が存在しない場合、または複雑すぎて価値がない場合は、GUI から再注文する間、少しの待ち時間を許容できます。

また、ブリッジ テーブルとも呼ばれる Closure テーブル (たくさん!)、Nested Intervals (正確な実装方法がわからず、適切な例や要点が現在存在しない?)、または B ツリー モデルも検討しています。これらが上記の4つの要件をどのように満たすか、まだよくわかりません。入れ子になった間隔でサブツリーとノードを再編成することは簡単に思え、パフォーマンスも良さそうです。適切なものを選択するのは非常に困難です。

私は間違いなくパフォーマンス（クエリ/読み取りパフォーマンス）、スケーラビリティ、ソートが必要なので、ソート順のあるクロージャーテーブルは非常に近いと思いましたが、クロージャーテーブルとディスクスペースのオーバーヘッドがツリーとしてどれだけ大きくなるか想像できませんノードが大きくなります。クロージャ テーブルとスケーラビリティについては、よくわかりません。これについて心配するのは間違っていますか?このタスクの最善の解決策は何ですか?

4

1 に答える 1

4

SQL に格納されたツリーのインデックス作成に使用される一般的なデータ構造は、頻繁に変更されないセットでの読み取りパフォーマンス用に設計および最適化されています。

たとえば、ネストされたセット モデルを使用している場合、ノードを追加または削除するには、ツリー全体を更新する必要があります (これは通常、テーブル全体を書き換えることを意味します)。読み取りには適していますが、書き込みにはあまり適していません。

書き込みパフォーマンスが重要な場合は、通常、(id, parent_id)再帰クエリを使用して生のタプルで作業する方がよいでしょう。その一方で、ダーティであることがわかっているツリー インデックスを null に設定します。読み取りパフォーマンスがより重要なアプリの領域では、ツリー インデックスの null 値をチェックしてサニティ チェックを行い、実際に使用する前に必要に応じてツリーのインデックスを再作成します。そうすれば、ツリーの絶え間ない書き換えを回避し、代わりに、読み取りに必要な場合にのみインデックスを再作成します。

(はるかに) 難しい別のアプローチは、ネストされたセットやネストされた区間などのバリエーションを使用することですが、整数の代わりに実数または浮動小数点数を使用します。これにより、ノードの挿入、移動、および削除を無料で行うことができますが、ストレージと算術/読み取りのオーバーヘッドが発生し、ネストされたセットの場合は子ノード数などのプロパティが失われます。ただし、病的なエッジケースに注意する必要もあります。つまり、浮動小数点型の精度制限に達したときに新しいノードに適合するように、定期的に (場合によっては先制的に) 「ガベージ コレクション」を行い、ツリーのインデックスの十分な大きさのチャンクを再インデックス化する必要があります。

(後者のバリエーションは、問題を回避しようとするために、精度のない数値を使用することです。しかし、数千の Postgres 内部によってまだ制限されるという意味で、実際には缶を蹴っています。また、数年前の私自身のテストでその限界に達するずっと前に、浮動小数点型を使用する場合と比較して、ストレージと算術のオーバーヘッドが重要になりました。)

「最高の」構造またはアプローチに関しては、実際には魔法の弾丸はありません...それぞれに、ユースケース (読み取りと書き込みの頻度) とセットのサイズに基づいた長所と短所があります。それらのそれぞれを比較して説明している文献がウェブ上にたくさんあります。

そうは言っても、CMS の場合は、最も快適な方法を使用することをお勧めします。書き込みが発生したときにその場でツリーのインデックスを再作成するか、書き込み時にツリーをダーティとしてマークし、必要に応じて再インデックスを作成します。ここでのポイントは、インデックスの再作成が適切に行われた場合 (= アプリが発行する無数のクエリではなく、plpgsql 関数または同等の機能を使用した場合)、数十万ノードのツリー全体のインデックス再作成に数百ミリ秒かかることです。せいぜい。ツリーが常に更新されていないと仮定すると、それはエンド ユーザーにとって完全に許容できるオーバーヘッドです。

于 2014-09-17T14:54:49.277 に答える