SQL で表現する階層関係のモデル

公開日: : 最終更新日:2014/01/26 SQL

次に着手する改修案件の事前調査をしていたところ、データの階層関係を「隣接リストモデル」で表現していた。何も疑うことなく、ボクもこれまで「隣接リストモデル」を使ってきたが、「確かこれってパフォーマンスが悪いんだよなぁ」と、ふと思い出した。

データの階層関係を表現する一般的なモデルを調べて見たのでメモしておく。

モデルは3種類

ちょっと調べてみると、まずこちらのサイトがヒットした。

こちらのサイトによると、モデルは3種類あるようだ。

  • 隣接リストモデル
  • 入れ子集合モデル
  • 経路列挙モデル

それぞれのモデルの概要は引用させてもらいます(問題があれば削除いたします)。

隣接リストモデル

それぞれのノード(階層データを構成する個々の要素)が親を保存しておきツリー構造をたどることによりデータ構造を表現します。
Oracleの階層問い合わせのようにSQL拡張がない場合(MySQLにはありません)は、別途プログラム等でループを組む必要がある場合があり、パフォーマンスが良くありません。
比較的理解しやすいですがMySQLで利用するには用途が限られます。

レコードに親 ID を持たせて親子関係を表現するモデル。階層が深くならないのであれば、このモデルを使い続けても OK なんだろう。

入れ子集合モデル

ノードを円と見なし親子関係を左右の番号を使用し円の包含関係として捉える事によりデータ構造を表現します。
検索に関しては隣接リストモデルと違い圧倒的有利であるが、直接の親・子やツリー構造をたどるのは複雑になります。
また、親子関係を左右の番号が追加、削除を繰り返すことにより歯抜けになります。(歯抜けが気持ち悪ければ正規化が必要)
構造は面白いが理解しづらくパフォーマンスが良くないところが見られますが、MySQLでも利用できます。

以前、Redmine のバージョンアップに関する記事を見たことがあって、その中で親子関係をこのモデルで実装していたことが触れられていた。何のことだかよく理解できなかったが、丁寧に解説されている記事を読んで「なるほど」と理解できた。

経路列挙モデル

各ノードに絶対パスをデータとして保存しデータ構造(UNIXのファイルシステムやURLの構造にそっくり)を表現します。
ノード自身のレコードに親子関係がパスとして含まれているので、SQL文が簡素になります。
また、パスは一意なりますし、MySQLでも正規表現を扱えるようになりましたので、極めて高い親和性と高いパフォーマンスが望めます。
MySQLで利用するには、この経路列挙モデルが一番親和性が高いように思います。

これは知らなかったので、検索してみると、これまた丁寧に解説されている記事があったのでリンクを貼っておく。素晴らしい。

Googleアドセンス用(PC)

  • このエントリーをはてなブックマークに追加
  • follow us in feedly

関連記事

記事はありませんでした

Googleアドセンス用(PC)

Message

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です


三 − 2 =

次のHTML タグと属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Googleアドセンス用(PC)

icatch-jersey_multi_pathparams
Jerseyの@PathParamはスラッシュの間に複数指定できる

http://hoge-api/user/{id}.{format}

icatch-vagrant_box_customize
VagrantのBoxファイルをカスタマイズして独自のBoxファイルを作成する

配布されている Vagrant の Box ファイルを使って検証環境を

icatch-2015-006-1
バリデーションチェックにJava8のOptionalを使ってスマートに書く(自分比)

Web アプリのバリデーションチェックにアノテーションを使うことが増え

icatch-2015-005-1
ユニットテストの偏りを防ぐ命名規則の付け方

ユニットテスト名に以下の命名規則を付けるようにして二ヶ月ぐらい経った。

icatch-2015-004-1
Vagrantで起動したCentOS上のOctopressをホストOSから確認する設定

タイトルの通りだが、Vagrant を使って起動した CentOS に

→もっと見る

PAGE TOP ↑