☰

リレーショナルデータベースに階層データを保存するオプションは何ですか? 質問する

tag-icon • tag-icon sql database tree relational-database hierarchical-data
リレーショナルデータベースに階層データを保存するオプションは何ですか? 質問する

良い概要

一般的に言えば、高速な読み取り時間 (ネストされたセットなど) と高速な書き込み時間 (隣接リスト) のどちらかを選択します。通常は、以下のオプションの組み合わせがニーズに最も適したものになります。以下は、詳細な情報です。

オプション

私が知っているものと一般的な特徴:

  1. 隣接リスト:
  • 列: ID、親ID
  • 実装が簡単です。
  • 安価なノードの移動、挿入、削除。
  • レベル、祖先と子孫、パスを見つけるのに費用がかかる
  • N+1を回避するには共通テーブル式これらをサポートするデータベース
  1. ネストされたセット（別名修正された事前順序ツリートラバーサル (MPTT)）
  • 列: 左、右
  • 安価な祖先、子孫
  • O(n/2)揮発性エンコーディングによる非常にコストのかかる移動、挿入、削除
  1. ブリッジテーブル（別名クローズテーブル /w トリガー）
  • 祖先、子孫、深さ（オプション）を含む個別の結合テーブルを使用します。
  • 安価な祖先と子孫
  • 挿入、更新、削除の書き込みコストO(log n)（サブツリーのサイズ）
  • 正規化されたエンコーディング: RDBMS 統計と結合のクエリ プランナーに適しています
  • ノードごとに複数の行が必要
  1. 系譜コラム（別名マテリアライズドパス、パス列挙）
  • 列: 系図 (例: 親/子/孫など)
  • プレフィックスクエリによる安価な子孫（例LEFT(lineage, #) = '/enumerated/path'）
  • 挿入、更新、削除の書き込みコストO(log n)（サブツリーのサイズ）
  • 非リレーショナル: 配列データ型またはシリアル化された文字列形式に依存
  1. ネストされた間隔
  • ネストされたセットと同様ですが、実数/浮動小数点数/小数点数を使用しているため、エンコードが揮発性ではありません (移動/挿入/削除が安価)
  • 実数/浮動小数点数/小数点数の表現/精度に問題がある
  • マトリックスエンコーディングバリアント「無料」の祖先エンコーディング（具体化されたパス）を追加しますが、線形代数のトリッキーさが加わります。
  1. フラットテーブル
  • 各レコードにレベルとランク (順序など) の列を追加する、変更された隣接リスト。
  • 反復処理やページネーションが簡単
  • 高価な移動と削除
  • 良い使い方: スレッド形式のディスカッション - フォーラム / ブログのコメント
  1. 複数の系統の列
  • 列: 系統レベルごとに 1 つ、ルートまでのすべての親を参照し、アイテムのレベルより下のレベルは NULL に設定されます。
  • 安い祖先、子孫、レベル
  • 安価な挿入、削除、葉の移動
  • 内部ノードの挿入、削除、移動にかかるコスト
  • 階層の深さに対するハード制限

データベース固有の注意事項

MySQL/MariaDB

オラクル

PostgreSQL

SQLサーバー

  • 概要
  • 2008年のオファー階層ID系統列アプローチに役立ち、表現できる深さを拡張すると思われるデータ型。

ベストアンサー1

私のお気に入りの答えは、このスレッドの最初の文で示唆されているとおりです。隣接リストを使用して階層を維持し、ネストされたセットを使用して階層を照会します。

これまでの問題は、隣接リストからネスト セットへの変換方法が恐ろしく遅いことでした。これは、ほとんどの人が変換に「プッシュ スタック」と呼ばれる極端な RBAR 方法を使用しており、隣接リストによるメンテナンスのシンプルさとネスト セットの素晴らしいパフォーマンスの涅槃に到達するにはコストがかかりすぎると考えられていたためです。その結果、ほとんどの人は、特に 100,000 ノード程度を超える場合は、どちらか一方に落ち着くことになります。プッシュ スタック方法を使用すると、MLM のユーザーが数百万ノードの小規模な階層と見なすものの変換に丸一日かかることがあります。

私は、不可能と思われるほどの速度で隣接リストをネストされたセットに変換する方法を考案して、Celko に少し競争させてみようと思いました。以下は、私の i5 ラップトップでのプッシュ スタック メソッドのパフォーマンスです。

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

そして、新しいメソッドの実行時間は次のとおりです (括弧内にプッシュ スタック メソッドが含まれます)。

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

はい、その通りです。100 万ノードが 1 分未満で変換され、10 万ノードが 4 秒未満で変換されました。

新しいメソッドの詳細とコードのコピーについては、次の URL をご覧ください。http://www.sqlservercentral.com/articles/Hierarchy/94040/

私は同様の方法を使用して、「事前集約」階層も開発しました。MLM 関係者や部品表を作成する人々は、この記事に特に興味を持つでしょう。http://www.sqlservercentral.com/articles/T-SQL/94570/

どちらかの記事をご覧になる場合は、「ディスカッションに参加する」リンクをクリックして、ご意見をお聞かせください。

おすすめ記事