Fertile Forest Model (2/n) RDB に於けるツリー構造データ [2]

ツリー構造データモデルで追加されるカラム

従来のデータベースエンジニア達は、RDB に於けるツリー構造データの問題を解決するために「隣接リストモデル」「経路列挙モデル」「入れ子集合モデル」「閉包テーブルモデル」の４種類のモデルを研究してきました。

各モデルで共通なのは、ツリー構造データを保存するための幾つかのカラムを RDB テーブルに追加する点です。追加されるカラムは、その役割から次の２種に分類されます。

階層構造カラム

階層構造を RDB テーブルへ格納するために必要なカラム

検索効率カラム

検索効率を上げるために追加するカラム

「階層構造カラム」は階層構造を再生するために必要な基礎部分で、検索クエリで検索条件を指定するためのカラムとしても使われます。

「検索効率カラム」は、部分木などの効率的な検索クエリを「階層構造カラム」だけで記述できない場合に追加されます。ツリー構造データを RDB に保存するだけが目的の場合には不要なカラムです。モデルによっては、「検索効率カラム」を使わないケースもあります。

優れたモデルの基準

ツリー構造データを扱うモデルの優劣は、次の２つの判定基準で決まります。

1. 検索クエリの実行速度が実用に耐えられる範囲である事
2. ツリー構造データのために追加される「延べカラム数」が少ない事

1. 検索クエリの実行速度

Web ページをめくって次のページが表示されるまで２分かかる Web サイトがあったとして、それを「実用に耐えられる速度」と考える人はいないと思います。現在の日本のインターネット環境では、５秒でも遅いと見做されるでしょう。データベースは Web ページの動的表示で使われる用途が多いので、人が遅さを感じるかどうかは Web ページをめくった時の待ち時間を基準として考えます。

検索クエリが index を参照できる場合は、レコード数が数億であったとしても実用に耐えられるだけの実行速度が出ます。反対に index が参照できないクエリでは、数十万のレコード数から検索する場合でも、条件によっては十分な実行速度は得られなくなります。ひとつ目の判定基準は、「index が参照できる検索クエリが書けるかどうか」と同義であると言えます。

ツリー構造データを RDB で扱う場合、「あるノードの部分木や子ノードを取得する検索クエリ」が最も多く利用されます。従って、「ツリー構造データモデルで実用的な検索クエリが書ける」というのは、次のように換言できます。

任意のノードの部分木や子ノードを取得する検索クエリを、
index を参照するように記述できる事

2.「延べカラム数」の少なさ

延べカラム数というのは、階層構造を保存するためのテーブルに保存するレコード数を考慮した表現です。テーブルにカラムが n 個しかなくても、ひとつのノードにつきレコードを m 個登録しなければならないなら、延べカラム数は「n * m 個」になります。ほとんどのモデルではレコード数 m = 1 になるので、一部のモデルを除いて「述べカラム数＝階層構造カラム数」と見做せます。

この延べカラム数が少ないほど、エコノミーで優れたモデルデザインであると言えます。データ量がすくなけばDBサーバーの容量も少なくて済みますし、検索速度への影響も軽減されるからです。

ツリー構造データモデルのまとめ

このページで紹介した内容は、以降の解説を理解する上で重要なポイントを含んでいます。以下の 3点を抑えてから、次節以降へお進み下さい。

1. ツリー構造データ用に RDB テーブルに追加されるカラムは、「階層構造カラム」と「検索効率カラム」の２種類がある
2. 部分木などの検索クエリを記述する際、index の参照が可能かどうかがモデルの優劣を決定する
3. 階層構造カラムや検索効率カラムの延べ数は、より少ないモデルが優る

リンク

• ツリー構造データをRDBで扱うための第五のモデル
• RDB に於けるツリー構造データ (1)
• RDB に於けるツリー構造データ (2)
• モデルデザイン
• ノード検索＜祖先ノード系＞
• ノード検索＜子孫ノード系＞
• ノード検索＜親戚ノード系＞
• ノード追加
• ノード移動