[sql] フラットテーブルをツリーに解析する最も効率的でエレガントな方法は何ですか?


6 Answers

ネストされたセットを使用する場合(変更済みプリオーダーツリートラバーサルとも呼ばれます)、ツリー構造全体またはツリー内のサブツリーを単一のクエリでツリー順に抽出することができます。ツリー構造を介して順序通りの経路を記述する列を管理する。

django-mpttでは、私は次のような構造を使いました:

id  parent_id  tree_id  level  lft  rght
--  ---------  -------  -----  ---  ----
 1       null        1      0    1    14
 2          1        1      1    2     7
 3          2        1      2    3     4
 4          2        1      2    5     6
 5          1        1      1    8    13
 6          5        1      2    9    10
 7          5        1      2    11   12

これは次のようなツリーを表します( idは各アイテムを表します)。

 1
 +-- 2
 |   +-- 3
 |   +-- 4
 |
 +-- 5
     +-- 6
     +-- 7

あるいは、入れ子にされた集合図として、 rght値とrght値がどのように働くかをより明白にする:

 __________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

見て分かるように、指定されたノードのサブツリー全体をツリー順にrghtするには、 lft値とrght値の間にlftrght値を持つすべての行を選択するだけです。 また、特定のノードの先祖のツリーを取得することも簡単です。

level列は、何よりも便宜上、非正規化のビットですtree_id列では、各最上位ノードのlftrght番号付けを再開できます。これにより、挿入、移動、削除の影響を受ける列の数がlftこれらの操作がギャップを作成または閉じるために行われるときには、それに応じて列を調整する必要があります。 私は、各操作に必要なクエリの周りを頭で囲んでいたときに、いくつかの開発ノートを作成しました。

実際にこのデータを使ってツリーを表示するという観点からは、各ノードごとに必要な表示を生成するのに十分な情報を与えるtree_item_iteratorユーティリティ関数を作成しました。

MPTTの詳細:

Question

順序付けられたツリー階層を格納するフラットなテーブルがあるとします。

Id   Name         ParentId   Order
 1   'Node 1'            0      10
 2   'Node 1.1'          1      10
 3   'Node 2'            0      20
 4   'Node 1.1.1'        2      10
 5   'Node 2.1'          3      10
 6   'Node 1.2'          1      20

ここに[id] Nameがある図があります。 ルートノード0は架空のものです。

                       [0] ROOT
                          /    \ 
              [1] Node 1          [3] Node 2
              /       \                   \
    [2] Node 1.1     [6] Node 1.2      [5] Node 2.1
          /          
 [4] Node 1.1.1

それをHTML(またはテキスト)として正しく整列され、正しくインデントされたツリーとして出力するには、どのような最小限のアプローチを使用しますか?

さらに、基本的なデータ構造(配列とハッシュマップ)、親/子参照の空想オブジェクト、ORM、フレームワークなし、ちょうど両手しか持たないと仮定します。 表は結果セットとして表され、ランダムにアクセスできます。

擬似コードまたは普通の英語は大丈夫です。これは純粋に概念的な質問です。

ボーナス問題:このようなツリー構造をRDBMSに格納する根本的に良い方法はありますか?

編集と追加

あるコメント作成者( Mark Besseyさん)の質問に答えるには:ルートノードは必ずしも表示されないため、必要ありません。 ParentId = 0は「これはトップレベルです」と表現するための規約です。 Order列は、同じ親を持つノードのソート方法を定義します。

私が話した「結果セット」は、ハッシュマップの配列として描くことができます(その用語にとどまる)。 私の例は既にそこにあることを意図していたからです。 いくつかの答えは余分に移動し、それを最初に構築しますが、それは大丈夫です。

ツリーは、任意に深くすることができます。 各ノードはN個の子を持つことができます。 しかし、私は正確に「何百万ものエントリー」ツリーを念頭に置いていませんでした。

私の選択したノード命名(「ノード1.1.1」)に頼るべきことを間違えてはいけません。 ノードは「Frank」または「Bob」とも呼ばれ、命名構造は暗示されません。これは単に読みやすくするためのものでした。

私は自分のソリューションを掲載しているので、皆さんはそれを引き出すことができます。




これはかなり古い質問ですが、多くの意見があるので、代替案を提示する価値があると思います。私の意見では非常にエレガントで解決策です。

ツリー構造を読み込むには、 再帰的な共通テーブル式 (CTE)を使用できます。 これは、一度にツリー構造全体をフェッチし、ノードのレベル、親ノードおよび親ノードの子内の順序についての情報を有する可能性を与える。

これがPostgreSQL 9.1でどのように動作するかを説明しましょう。

  1. 構造を作成する

    CREATE TABLE tree (
        id int  NOT NULL,
        name varchar(32)  NOT NULL,
        parent_id int  NULL,
        node_order int  NOT NULL,
        CONSTRAINT tree_pk PRIMARY KEY (id),
        CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id) 
          REFERENCES tree (id) NOT DEFERRABLE
    );
    
    
    insert into tree values
      (0, 'ROOT', NULL, 0),
      (1, 'Node 1', 0, 10),
      (2, 'Node 1.1', 1, 10),
      (3, 'Node 2', 0, 20),
      (4, 'Node 1.1.1', 2, 10),
      (5, 'Node 2.1', 3, 10),
      (6, 'Node 1.2', 1, 20);
    
  2. クエリを書く

    WITH RECURSIVE 
    tree_search (id, name, level, parent_id, node_order) AS (
      SELECT 
        id, 
        name,
        0,
        parent_id, 
        1 
      FROM tree
      WHERE parent_id is NULL
    
      UNION ALL 
      SELECT 
        t.id, 
        t.name,
        ts.level + 1, 
        ts.id, 
        t.node_order 
      FROM tree t, tree_search ts 
      WHERE t.parent_id = ts.id 
    ) 
    SELECT * FROM tree_search 
    WHERE level > 0 
    ORDER BY level, parent_id, node_order;
    

    結果は次のとおりです。

     id |    name    | level | parent_id | node_order 
    ----+------------+-------+-----------+------------
      1 | Node 1     |     1 |         0 |         10
      3 | Node 2     |     1 |         0 |         20
      2 | Node 1.1   |     2 |         1 |         10
      6 | Node 1.2   |     2 |         1 |         20
      5 | Node 2.1   |     2 |         3 |         10
      4 | Node 1.1.1 |     3 |         2 |         10
    (6 rows)
    

    ツリーノードは、深さレベルで順序付けられます。 最終出力では、それを後続の行に表示します。

    各レベルについて、親内のparent_idとnode_orderによって順序付けられます。 これは、アウトプットリンクノードに親ノードをこの順序で提示する方法を示しています。

    このような構造を持つことで、HTMLで本当に素敵なプレゼンテーションを作るのは難しくありません。

    再帰CTEは、 PostgreSQL、IBM DB2、MS SQL ServerおよびOracleで利用できます

    再帰的なSQLクエリについてさらに詳しく知りたい場合は、お気に入りのDBMSのドキュメントをチェックするか、このトピックに関する2つの記事を読んでください:




ルート要素がゼロであることを知っていると仮定すると、テキストに出力する擬似コードは次のようになります。

function PrintLevel (int curr, int level)
    //print the indents
    for (i=1; i<=level; i++)
        print a tab
    print curr \n;
    for each child in the table with a parent of curr
        PrintLevel (child, level+1)


for each elementID where the parentid is zero
    PrintLevel(elementID, 0)



あなたの例に示されているように、要素がツリー順であれば、次のPythonの例のようなものを使うことができます:

delimiter = '.'
stack = []
for item in items:
  while stack and not item.startswith(stack[-1]+delimiter):
    print "</div>"
    stack.pop()
  print "<div>"
  print item
  stack.append(item)

これは、ツリー内の現在の位置を表すスタックを維持することです。 テーブルの各要素について、現在の項目の親を見つけるまでスタック要素をポップします(一致するdivを閉じる)。 次に、そのノードの開始点を出力し、それをスタックにプッシュします。

ネストされた要素ではなくインデントを使用してツリーを出力する場合は、単にprintステートメントをスキップしてdivを出力し、各項目の前にスタックのサイズの倍数に等しい数のスペースを出力することができます。 例えば、Pythonでは:

print "  " * len(stack)

このメソッドを使用して、ネストされたリストまたはディクショナリのセットを簡単に作成することもできます。

編集:あなたの説明から、名前がノードのパスではないことがわかりました。 これは代替アプローチを示唆しています。

idx = {}
idx[0] = []
for node in results:
  child_list = []
  idx[node.Id] = child_list
  idx[node.ParentId].append((node, child_list))

これは、タプル(!)の配列のツリーを構築します。 idx [0]はツリーのルートを表します。 配列の各要素は、ノード自体とそのすべての子のリストからなる2つのタプルです。 構築したら、IDでノードにアクセスしない限り、idx [0]を保持してidxを破棄することができます。




まあ、選択肢があれば、私はオブジェクトを使用しています。 私はそれぞれのオブジェクトがchildrenコレクションを持つ各レコードのオブジェクトを作成し、Idがキーであるassoc配列(/ハッシュテーブル)にそれらをすべて格納します。 コレクションを一度爆撃し、関連する子フィールドに子供を追加します。 シンプル。

しかし、いくつかの良いOOPの使用を制限することによってあなたが楽しくないので、おそらく私は繰り返しに基づいています:

function PrintLine(int pID, int level)
    foreach record where ParentID == pID
        print level*tabs + record-data
        PrintLine(record.ID, level + 1)

PrintLine(0, 0)

編集:これは他のいくつかのエントリに似ていますが、私はそれが少しきれいだと思います。 追加することの1つは、これは非常にSQLを大量に使用することです。 それは厄介です。 選択肢があれば、OOPルートに進んでください。




階層構造のためにneo4jのようなnosqlツールを使用することを考えてください。 例えば、linkedinのようなネットワーク化されたアプリケーションはcouchbase(別のnosqlソリューション)

ただし、データマート・レベルの問合せに対してのみnosqlを使用し、トランザクションを格納/保持しない




SQLインデックスの内部btree表現を利用する本当に良いソリューションがあります。 これは、1998年頃に行われた素晴らしい研究に基づいています。

以下は、(mysqlの)テーブル例です。

CREATE TABLE `node` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `tw` int(10) unsigned NOT NULL,
  `pa` int(10) unsigned DEFAULT NULL,
  `sz` int(10) unsigned DEFAULT NULL,
  `nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
  PRIMARY KEY (`id`),
  KEY `node_tw_index` (`tw`),
  KEY `node_pa_index` (`pa`),
  KEY `node_nc_index` (`nc`),
  CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)

ツリー表現に必要な唯一のフィールドは次のとおりです。

  • tw:左から右のDFS Pre-orderインデックス。ルートは1です。
  • pa:親ノードへの参照(twを使用)。rootにはnullがあります。
  • sz:それ自身を含むノードのブランチのサイズ。
  • nc:は構文的な砂糖として使われます。 tw + ncであり、ノードの「次の子」のtwを表します。

以下は、twで指定された24個のノードの母集団の例です:

+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|   2 | A       |  2 |    1 |   14 |   16 |
|   3 | AA      |  3 |    2 |    1 |    4 |
|   4 | AB      |  4 |    2 |    7 |   11 |
|   5 | ABA     |  5 |    4 |    1 |    6 |
|   6 | ABB     |  6 |    4 |    3 |    9 |
|   7 | ABBA    |  7 |    6 |    1 |    8 |
|   8 | ABBB    |  8 |    6 |    1 |    9 |
|   9 | ABC     |  9 |    4 |    2 |   11 |
|  10 | ABCD    | 10 |    9 |    1 |   11 |
|  11 | AC      | 11 |    2 |    4 |   15 |
|  12 | ACA     | 12 |   11 |    2 |   14 |
|  13 | ACAA    | 13 |   12 |    1 |   14 |
|  14 | ACB     | 14 |   11 |    1 |   15 |
|  15 | AD      | 15 |    2 |    1 |   16 |
|  16 | B       | 16 |    1 |    1 |   17 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
|  18 | D       | 23 |    1 |    1 |   24 |
|  19 | E       | 24 |    1 |    1 |   25 |
+-----+---------+----+------+------+------+

すべてのツリー結果は非再帰的に実行できます。 たとえば、tw = '22 'のノードの祖先のリストを取得するには、

祖先

select anc.* from node me,node anc 
where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw 
order by anc.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

兄弟姉妹と子供たちは自明です。

子孫

例えば、tw = 17に根ざしたノードの集合(枝)。

select des.* from node me,node des 
where me.tw=17 and des.tw < me.nc and des.tw >= me.tw 
order by des.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

その他の注意事項

この方法は、挿入や更新よりもはるかに多くの読み込みがある場合に非常に便利です。

ツリー内のノードの挿入、移動、または更新はツリーの調整が必要なため、アクションを開始する前にテーブルをロックする必要があります。

twインデックスとsz(分岐サイズ)の値は、挿入ポイントの後のすべてのノードとすべての祖先に対してそれぞれ更新する必要があるため、挿入/削除コストが高くなります。

分岐を移動するには、分岐のtw値を範囲外に移動する必要があります。そのため、分岐を移動するときに外部キーの制約を無効にする必要があります。 ブランチの移動には基本的に4つのクエリが必要です。

  • ブランチを範囲外に移動します。
  • それが残ったギャップを閉じます。 (残りのツリーは現在正規化されています)。
  • それがどこに行くのギャップを開きます。
  • ブランチを新しい位置に移動します。

ツリークエリの調整

ツリー内のギャップの開閉は、作成/更新/削除メソッドで使用される重要なサブ関数なので、ここに含めます。

ダウンサイジングとアップサイジングを行うかどうかを表すフラグとノードのtwインデックスの2つのパラメータが必要です。 したがって、例えばtw = 18(分岐サイズが5)です。 我々がダウンサイジングを行っていると仮定しましょう(twを削除する) - これは、次の例の更新で '+'の代わりに ' - 'を使用していることを意味します。

最初に(わずかに変更された)祖先関数を使用してsz値を更新します。

update node me, node anc set anc.sz = anc.sz - me.sz from 
node me, node anc where me.tw=18 
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));

次に、twが削除されるブランチよりも高いものに対してtwを調整する必要があります。

update node me, node anc set anc.tw = anc.tw - me.sz from 
node me, node anc where me.tw=18 and anc.tw >= me.tw;

次に、paのtwが削除されるブランチよりも高いものの親を調整する必要があります。

update node me, node anc set anc.pa = anc.pa - me.sz from 
node me, node anc where me.tw=18 and anc.pa >= me.tw;



Related