59

Tree と TreeNode を組み合わせたデータ ツリー構造を作成しています。ツリーには、データに対するルートおよび最上位レベルのアクションが含まれます。UI ライブラリを使用して、ツリーを TreeView にバインドできる Windows フォームにツリーを表示しています。

このツリーとノードを DB に保存する必要があります。ツリーを保存し、次の機能を取得するための最良の方法は何ですか?

  1. 直感的な実装。
  2. 簡単なバインディング。ツリーから DB 構造への移動とその逆 (存在する場合) が容易になります。

2つのアイデアがありました。1 つ目は、データをテーブル内の 1 つのライナーにシリアル化することです。2 つ目は、テーブルに保存することですが、データ エンティティに移動すると、変更されたノードのテーブルの行の状態が失われます。

何か案は？

4

8 に答える 8

52

SQL-Antipatterns に関するこのスライドシェアをブックマークしました。これには、いくつかの代替案が説明されています: http://www.slideshare.net/billkarwin/sql-antipatterns-strike-back?src=embed

そこからの推奨事項は、Closure Table を使用することです (スライドで説明されています)。

要約は次のとおりです (スライド 77)。

                  | Query Child | Query Subtree | Modify Tree | Ref. Integrity
Adjacency List    |    Easy     |     Hard      |    Easy     |      Yes
Path Enumeration  |    Easy     |     Easy      |    Hard     |      No
Nested Sets       |    Hard     |     Easy      |    Hard     |      No
Closure Table     |    Easy     |     Easy      |    Easy     |      Yes
于 2010-11-28T16:43:44.590 に答える
41

最も簡単な実装は、隣接リスト構造です。

id  parent_id  data

ただし、一部のデータベース、特にMySQLでは、このモデルの処理にいくつかの問題があります。これは、再帰クエリを実行する機能が必要であるためMySQLです。

別のモデルはネストされたセットです:

id lft rgt data

ここでlft、 とrgtは、階層を定義する任意の値です (すべての子のlftは、親の内にrgtある必要があります) 。lftrgt

これには再帰クエリは必要ありませんが、遅くなり、維持するのが難しくなります。

ただし、MySQLこれはSPATIALアビリティを使用して改善できます。

私のブログでこれらの記事を参照してください。

詳細な説明については。

于 2010-02-01T10:21:01.750 に答える
11

おそらく、標準SQLでツリーを操作する最速の方法であるマテリアライズドパスソリューションについて誰も言及していないことに驚いています。

このアプローチでは、ツリー内のすべてのノードに列パスがあり、ルートからノードまでのフルパスが格納されます。これには、非常に単純で高速なクエリが含まれます。

テーブルノードの例を見てください：

+---------+-------+
| node_id | path  |
+---------+-------+
| 0       |       |
| 1       | 1     |
| 2       | 2     |
| 3       | 3     |
| 4       | 1.4   |
| 5       | 2.5   |
| 6       | 2.6   |
| 7       | 2.6.7 |
| 8       | 2.6.8 |
| 9       | 2.6.9 |
+---------+-------+

ノードxの子を取得するには、次のクエリを記述できます。

SELECT * FROM node WHERE path LIKE CONCAT((SELECT path FROM node WHERE node_id = x), '.%')

LIKE句を高速に実行するには、列パスにインデックスを付ける必要があることに注意してください。

于 2012-11-02T21:21:06.773 に答える
6

データのクエリと更新の方法によって異なります。すべてのデータを 1 つの行に格納すると、基本的に、すべてのデータを書き換えずにクエリを実行したり部分的に更新したりできない単一のユニットになります。

各要素を行として保存する場合は、最初に MySQL での階層データの管理(MySQL 固有ですが、アドバイスは他の多くのデータベースにも当てはまります) を読む必要があります。

ツリー全体にしかアクセスしない場合、隣接リスト モデルにより、再帰クエリを使用せずにルートの下にあるすべてのノードを取得することが難しくなります。ヘッドにリンクする余分な列を追加するSELECT * WHERE head_id = @idと、1 つの非再帰クエリでツリー全体を取得できますが、データベースが非正規化されます。

一部のデータベースには、階層データの格納と取得を容易にするカスタム拡張機能があります。たとえば、Oracle にはCONNECT BYがあります。

于 2010-02-01T10:19:03.013 に答える
0

最善の方法は、各ノードに id と parent_id を与えることだと思います。ここで、親 id は親ノードの id です。これにはいくつかの利点があります

  1. ノードを更新したいときは、そのノードのデータを書き換えるだけです。
  2. 特定のノードのみを照会したい場合、必要な情報を正確に取得できるため、データベース接続のオーバーヘッドが少なくなります
  3. 多くのプログラミング言語には、mysql データを XML または json に変換する機能があり、API を使用してアプリケーションを簡単に開くことができます。
于 2011-04-06T16:29:40.480 に答える
0

各ノード行に (通常のノード データに加えて) 親 ID が含まれるテーブル「ノード」のようなもの。root の場合、親は NULL です。

もちろん、これにより子の検索に時間がかかりますが、実際のデータベースは非常に単純になります。

于 2010-02-01T10:21:45.773 に答える