データベース

RDBで階層構造を扱う方法

カテゴリーとか階層構造を持ったデータをMySQLで扱いたい。
どうすりゃいいのさ?

リンク

まずは、Google検索!
MySQL 階層構造 - Google検索

いろいろヒットしました!

  • MySQLで階層化データを使うには
    http://www.makizou.com/archives/1616

    リレーショナルデータベースの機能内で階層データを扱う方法は以下の3モデルがあります。

    - 隣接リストモデル [Adjacency List Model]

    - 入れ子集合モデル [Nested Set Model]

    - 経路列挙モデル [Path Emuneration Model](もしくは、経路実体化モデル [Materialized Path Model])

隣接リストモデル

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

入れ子集合モデル

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

経路列挙モデル

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

経路列挙モデルでOK

経路列挙モデル

位置情報をファイルシステムと同じ方法で持つ。直観的に分かりやすいので良さげ。

経路列挙モデルの並び替え

経路列挙モデルで、同じ階層のデータ(同じ親ノードにぶら下がっている子ノード同士)を並び替えるにはどうしたら良いか?

sortフラグを持たせて、大小の数値を付与すればいいの?
並び順まで考えたら、入れ子モデルの方が良いだろうか?

経路列挙モデルは、階層構造の上下関係のデータを持っているけど、並び順のデータは表現できない。

並び順を指定するには、入れ子モデルの方が簡潔だろうか?
…ということで入れ子モデルに変更w

入れ子モデル

入れ子モデルには、

  • 入れ子集合モデル
  • 入れ子区間モデル
    の二つが紹介されていました。

入れ子区間モデル

SQLで木と階層構造のデータを扱う(3)――入れ子区間モデル

入れ子集合モデルには、整数を座標に使っているため、更新時のパフォーマンスが悪いという欠点がありました。それを克服するため、整数から有理数へ一般化したモデル。

第6回 SQLで木構造を扱う~入れ子区間モデル (1)もしも無限の資源があったなら
http://gihyo.jp/dev/serial/01/sql_academy2/000601

データの追加を繰り返すと、識別子の少数化がどんどん進むので、整数を振り直す(正規化)する処理を追加してみるとか。
=[lft][rgt]を整数に直す処理

並替え可能な経路列挙モデル

ここまで考えて、経路列挙モデルでsortするアイデアを思いついてしまった!!!

  • sortフラグを持たせ、並び順を示す数値を入れる。
  • sortフラグの数値は、整数ではなく実数を使う。
    =入れ子区間モデルと同じアイデア
  • 実数で見づらければ、整数に正規化する処理を入れる。

並び替えの処理

これはSQLだと複雑になりそうなので、プログラム側で処理させる。

  • 同じ階層のデータ同士は並び替え可能にする。
  • 異なる階層のデータ同士は並び替えを不可能にする。
    その判別処理をプログラムで行なう。

テーブル設計

カラム名データ型内容
idintカテゴリーID
nametextカテゴリー名
pathtextノードのパス情報
sortfloat並び順
sort_normalint並び順を正規化するための一時的な作業用カラム。無くてもOK?

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2011-06-08 (水) 18:44:50 (2238d)