16

私はテーブルにツリー構造を持っており、それは私が子供を素早く見つけることを可能にするために具体化されたパスを使用しています。ただし、スレッド化されたフォーラムの返信で予想されるように、結果を深さ優先で並べ替える必要もあります。

 id | parent_id | matpath |          created           
----+-----------+---------+----------------------------
  2 |         1 | 1       | 2010-05-08 15:18:37.987544
  3 |         1 | 1       | 2010-05-08 17:38:14.125377
  4 |         1 | 1       | 2010-05-08 17:38:57.26743
  5 |         1 | 1       | 2010-05-08 17:43:28.211708
  7 |         1 | 1       | 2010-05-08 18:18:11.849735
  6 |         2 | 1.2     | 2010-05-08 17:50:43.288759
  9 |         5 | 1.5     | 2010-05-09 14:02:43.818646
  8 |         6 | 1.2.6   | 2010-05-09 14:01:17.632695

したがって、最終結果は実際には次のように並べ替える必要があります。

 id | parent_id | matpath |          created
----+-----------+---------+----------------------------
  2 |         1 | 1       | 2010-05-08 15:18:37.987544
  6 |         2 | 1.2     | 2010-05-08 17:50:43.288759
  8 |         6 | 1.2.6   | 2010-05-09 14:01:17.632695
  3 |         1 | 1       | 2010-05-08 17:38:14.125377
  4 |         1 | 1       | 2010-05-08 17:38:57.26743
  5 |         1 | 1       | 2010-05-08 17:43:28.211708
  9 |         5 | 1.5     | 2010-05-09 14:02:43.818646
  7 |         1 | 1       | 2010-05-08 18:18:11.849735

どうすればそれを解決できますか？ストレートSQL（これはPostgreSQL 8.4）でそれを行うことができますか、それともこのテーブルに追加情報を追加する必要がありますか？

更新：ソート基準をより適切に説明しようとしています。

ID「1」がフォーラムへのルート投稿であり、「1」で始まる「matpath」を持つすべてのものがその投稿の子であると想像してください。したがって、ID 2から5は1への直接応答であり、「1」のマットパスを取得します。ただし、id 6は1への直接の応答ではなく2の応答であるため、1.2のマットパスを取得します。これは、すべてのIDが表に示されている、適切にネストされたスレッドフォーラムの場合、フォーラムの構造は次のようになることを意味します。したがって、順序付けの要件は次のとおりです。

* id 1 (root post)
    * id 2
        * id 6
            * id 8
    * id 3
    * id 4
    * id 5
        * id 9
    * id 7
4

5 に答える 5

18

あなたの具体化された道は正しくないと思います。

このようなものをソートするためにどのようなロジックを取得しますか

1
1.2
1
1.5

2番目の1が最初の1と一緒になっていないのはなぜですか？

あなたが持っていた場合

1
1.2
2
2.5

これは些細なことです。

編集：私はあなたの例を見ました、そしてあなたは行のマテリアライズドパスを保存していませんが、あなたは親行のマテリアライズドパスを保存しています。行の実体化されたパスが実際にどのように見えるかを次に示します。次のように保存した場合、9つを超えるブランチがない場合は、matpathで直接並べ替えることができます。

 id | parent_id | matpath   |          created
----+-----------+-----------+----------------------------
  2 |         1 | 1.2       | 2010-05-08 15:18:37.987544
  6 |         2 | 1.2.6     | 2010-05-08 17:50:43.288759
  8 |         6 | 1.2.6.8   | 2010-05-09 14:01:17.632695
  3 |         1 | 1.3       | 2010-05-08 17:38:14.125377
  4 |         1 | 1.4       | 2010-05-08 17:38:57.26743
  5 |         1 | 1.5       | 2010-05-08 17:43:28.211708
  9 |         5 | 1.5.9     | 2010-05-09 14:02:43.818646
  7 |         1 | 1.7       | 2010-05-08 18:18:11.849735

そうでなければ（> 9）あなたは次のmatpathようなものに変える必要があります

001.002.006
001.002.006.008

最大999のブランチをサポートします。

ご注意ください

  • 0001.0002.0006受け入れられた回答よりも短いフィールドを提供するなど、4桁の固定数字を使用するアプローチでも
  • ユーザー関数を使用して、matpathを解析し、その場でソート値を生成できます。
  • この形式でmatpathを直接保存できます（他にもいくつかの優れたプロパティがあります）
于 2010-05-09T13:21:32.247 に答える
9

私は通常、このために、のようなものと呼ばれる追加の列を作成しますSortPath。これには、並べ替える必要のあるデータが連結されて含まれます。その列はタイプvarcharであり、文字列としてソートされます。このようなもの：

id | parent_id | matpath |          created            |                   sortpath
---+-----------+---------+-----------------------------+--------------------------------------------------------------------------------------
 2 |         1 | 1       | 2010-05-08 15:18:37.987544  | 2010-05-08 15:18:37.987544-2
 6 |         2 | 1.2     | 2010-05-08 17:50:43.288759  | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6
 8 |         6 | 1.2.6   | 2010-05-09 14:01:17.632695  | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6.2010-05-09 14:01:17.632695-8
 3 |         1 | 1       | 2010-05-08 17:38:14.125377  | 2010-05-08 17:38:14.125377-3
 4 |         1 | 1       | 2010-05-08 17:38:57.26743   | 2010-05-08 17:38:57.267430-4 
 5 |         1 | 1       | 2010-05-08 17:43:28.211708  | 2010-05-08 17:43:28.211708-5
 9 |         5 | 1.5     | 2010-05-09 14:02:43.818646  | 2010-05-08 17:43:28.211708-5.2010-05-09 14:02:43.818646-9
 7 |         1 | 1       | 2010-05-08 18:18:11.849735  | 2010-05-08 18:18:11.849735-7

ここで注意すべき点がいくつかあります。

  • sortpath文字列として並べ替えられるため、正しく並べ替えるには、すべての日付の長さが同じであることが重要です。たとえば、列2010-05-08 17:38:57.26743に余分なゼロがどのように追加されているかを観察しsortpathます。
  • 各ノードのPKをその日付の最後に追加しました。これは、まったく同じ日付の2つの行がある場合、追加する追加データのために、それらが常に同じ順序で返されるようにするためです。
  • 現在のノードの日付をで表示しているので、データは私が書いた方法では非対称に見えますがsortpath、ではありませんmatpath。私は両方でそれを見たいと思います。
  • ノードID1の日付もそれぞれの先頭に配置することをお勧めしsortcolumnます。これは、一度に複数のフォーラムを照会したい場合（おそらくそうしないでしょう）、それでも正しくソートされるようにするためです。
于 2010-05-09T13:19:34.723 に答える
7

受け入れられた解決策がまったく意味をなさない理由がわかりません。これは機能しますが、@ Unreasonのソリューション（マテリアライズされたパスにIDを埋め込むだけ）よりも正規化されておらず、効率も低くなります（ディスク容量やインデックスが増えるなど）。

OPが直面するシナリオ全体は、@ Unreasonが正しく指摘しているように、マテリアライズドパス（MP）の実装が正しくないという事実に起因しているようです。OPは、現在のノードではなく、親にMPを提供しました。受け入れられたソリューションでは、SortPath列は現在のノードへのマテリアライズドパスを提供することでこれを修正します（今回は主キーの代わりに日付-なぜ？-を使用します）。

参考までに、次の抜粋を検討してください。

マテリアライズドパス

このアプローチでは、各レコードはルートへのパス全体を格納します。前の例では、KINGがルートノードであると仮定します。次に、ename ='SCOTT'のレコードは、パスSCOTT->JONES->KINGを介してルートに接続されます。最新のデータベースでは、ノードのリストを単一の値として表すことができますが、マテリアライズドパスはそれよりずっと前に発明されたため、規則は、何らかの区切り文字で連結されたノードのプレーン文字列に固執しました。よく '。' また '/'。

于 2012-07-14T19:17:01.940 に答える
6

パディングに関する@Unreasonの回答は機能しますが、この問題に対する私自身の発明であると私が信じる別の解決策を提供したいと思います。

バイトストリームを作成する関数を探していますf(x)=b_1b_2..b_i（SOではMatJaxは申し訳ありません）。ここb_iで、はバイトです。2つのバイトストリームが最初の異なるバイトと同じように比較されることがわかっています。そのような関数が必要ですf(x)<f(y) iff x<y。

0と同じ長さにパディングすると、この目標を簡単に達成できます。あなたは2つの数字を取り、最初の非ゼロバイトを見て、そこにいます。

Steven Wittens（acko.net）は、約8年前にDrupalコアに別のトリックを導入しました。それは、文字列の前の桁数を別の桁として配置することです。したがって、番号97685は文字になり5 9 7 6 8 5ます。これも機能します。最初に長さバイトを見てください。同じでない場合は、大きいほど確実に大きくなります。それを超えると、2つの数値が同じ長さであることがわかります。彼はまた、すべての文字の16進数のように、0-9a-zが数字である36進数を使用しました。このエンコーディングには、最初の36ノードに2バイト、次の1260ノードに3バイトが必要です。

パディングもこの狡猾な可変長エンコーディングも、読みやすさのために含まれていることが多いものの、マテリアライズドパスにセパレータを必要としないことに注意してください。

numconvはbase85エンコーディングをサポートしていますが、大文字と小文字を区別する照合が必要です。小文字を削除すると、まだbase68が残っている94個のASCII文字があります。

ただし、「binary」フィールドを使用する場合は、base256を実行できます。狡猾なエンコーディングの代わりに、数値を一連のバイトとして書き込み、全体にバイトストリームの長さを1バイトとしてプレフィックスとして付けます。これにより、2^2048程度よりも小さいツリーをエンコードできます。最初の256ノードでは2バイトを使用し、次の65280では3バイトを使用しています。これはすでに非常に効率的です。

関数を指名しutf8encode(x)ます。それを考慮してください！バイトソートではなくビットソートに移行する必要がありますが、結果は変わりません。左端のゼロビットを見つけてください。他の文字列に1が含まれている場合は、UTF-8エンコーディングが長くなるため、間違いなく大きくなります。同じ場所に最初のゼロがある場合は、同じ長さのビット文字列があり、比較に適しています。

それは素晴らしいことですが、セパレーターについてはどうでしょうか。UTF-8アルゴリズムを純粋にビットストリームを作成するアルゴリズムと見なすと、31ビットの数値を処理できるため、20億ノード未満のツリーで機能します。マテリアライズされたパスは、よく比較できるUTF-8エンコード番号のビットストリームになります。左端の同一のUTF-8エンコード番号を破棄すると、前の段落に戻ります。QED

セパレータやプレフィックスバイトは必要ないため、最初の128ノードを1バイトにエンコードし、次の1920ノードを2バイトにエンコードし、最大65535バイトを3バイトにエンコードできます。4バイトの場合、base256が優先されます。非常に大きなツリーの場合、UTF-8をバイトストリームへの0-2147483647のエンコーダーとして扱うことができます。したがって、base2147483647エンコーディングとして使用できます：D

要約すると、UTF-8は小さなツリーに最適であり、20億ノード未満のbase256よりもそれほど悪くはありません。それを超えると、2^2048程度までprefixed-with-length-base256が勝ちます。それを超えると、prefixed-with-length-base2147483647が勝ち、それ以上のものはありません。

于 2014-02-10T05:15:17.690 に答える
3

ストレートSQLでこれを行う簡単な方法は考えられません。ここでは、matpathではなく、node_pathを使用します。node_pathはmatpathです||'。'||id

 id | parent_id | node_path |          created           
----+-----------+---------+----------------------------
  2 |         1 | 1.2       | 2010-05-08 15:18:37.987544
  3 |         1 | 1.3       | 2010-05-08 17:38:14.125377
  4 |         1 | 1.4       | 2010-05-08 17:38:57.26743
  5 |         1 | 1.5       | 2010-05-08 17:43:28.211708
  7 |         1 | 1.7       | 2010-05-08 18:18:11.849735
  6 |         2 | 1.2.6     | 2010-05-08 17:50:43.288759
  9 |         5 | 1.5.9     | 2010-05-09 14:02:43.818646
  8 |         6 | 1.2.6.8   | 2010-05-09 14:01:17.632695

次に、node_pathに基づいてツリーを並べ替え、並べ替えを実行した回数によって並べ替えフィールドを定義します。

split_part（node_path、'。'、recursion_depth）でのplpgsqlソートのカスタム再帰関数が機能します。split_partからのNULL値をチェックする必要があります（そしてそれらを無視します）。

于 2010-05-09T14:46:19.947 に答える