フラットテーブルからツリー階層を効率的に構築し、RDBMSでそのストレージを最適化する方法は？

フラットテーブルからツリー構造を抽出

効率的かつ洗練されたデータ構造分析

「Id」、「Name」、「ParentId」、「Order」などの列を含むフラットなデータ構造があり、目的はツリー構造を効率的に構築することであるとします。配列やハッシュ テーブルなどの基本的なデータ構造のみが利用可能な場合、有効なアプローチには次のものが含まれます:

1. ハッシュ テーブルを作成します: キーが「Id」値であり、値が対応する「Name」値であるハッシュ テーブルを初期化します。
2. データ テーブルをループします: テーブル内の各行について、その 'Id' 値と 'ParentId' 値を取得し、それらをハッシュ テーブルに追加します。
3. ツリーを再帰的に構築します: ルート ノード ('ParentId' を 0 に設定) から開始して、ツリーを再帰的に走査します。各ノードについて、「ParentId」から「Id」を取得し、ハッシュ テーブルでその名前を取得することで、子ノードがあるかどうかを確認します。
4. 結果を組み立てる: ツリーをトラバースしながら、目的の出力形式 (HTML やテキストなど) を組み立てます。

RDBMS のツリー構造のストレージを最適化します

質問で言及されているフラット テーブル構造は一般的なアプローチですが、リレーショナル データベースのツリー ストレージを最適化する他の方法もあります。

1. クロージャテーブル:

クロージャ テーブルには、各祖先と子孫の関係が明示的に保存されます。これにより、SQL クエリを使用して子孫または祖先を効率的に取得できるようになります。

例:

<code class="language-sql">CREATE TABLE ClosureTable (
  ancestor_id INT REFERENCES MyTable(id),
  descendant_id INT REFERENCES MyTable(id),
  PRIMARY KEY (ancestor_id, descendant_id)
);</code>

2. ネストされたセット:

ネストされたセットは、ツリー内の各ノードに整数の範囲を割り当てます。範囲間隔は、ツリー階層内のノードの位置を定義します。

例:

テーブル:

<code class="language-sql">CREATE TABLE NestedSets (
  id INT PRIMARY KEY,
  left_value INT,
  right_value INT
);</code>

ツリー構造:

<code>                       |-----|   [0, 9]   |-----|
                       |     |          |     |
                 |-----|     |-----|     |-----|
                 | [0, 2]   |     | [4, 6]   |     | [8, 9]  |
                 |         |     |         |     |        |
                |-----|   |-----|   |-----|   |-----|
                | [0, 1] |   | [2, 3] |   | [4, 5] |   | [6, 7] |
                |       |   |       |   |       |   |       |
               | [0, 0] |   | [2, 2] |   | [4, 4] |   | [6, 6] |</code>

3. 隣接リスト:

隣接リストは、id とparent_id の 2 つの列を持つテーブルとしてツリーを表します。各行はノードを表し、parent_id 列はその親ノードを指します。

例:

<code class="language-sql">CREATE TABLE AdjacencyList (
  id INT PRIMARY KEY,
  parent_id INT REFERENCES AdjacencyList(id)
);</code>

ツリー ストレージ最適化テクノロジの選択は、データ サイズ、クエリ モード、データベースのパフォーマンス要件などの要因によって異なります。

追加の質問: はい、上記の手法 (クロージャ テーブル、ネストされたセット、隣接リスト) を使用して、RDBMS にツリー構造を格納する根本的により良い方法があります。

以上がフラットテーブルからツリー階層を効率的に構築し、RDBMSでそのストレージを最適化する方法は？の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。