ハイブリッドモデル
従来の 4モデルには、面白いトレードオフが見られます。下の表は、部分木と親子ノードを検索するクエリが各モデルに於いてスマートに記述できるかどうかの一覧です。ここでは、ハイブリッドモデルを説明するために、評価を◎○×だけで表現しています。
| モデル名 | 部分木の検索 | 親子ノードの検索 |
|---|---|---|
| 隣接リストモデル | × | ◎ |
| 経路列挙モデル | ○ | × |
| 入れ子集合モデル | ○ | × |
| 閉包テーブルモデル | ○ | × |
部分木の検索に優れている入れ子集合モデルや閉包テーブルモデルは、親や子の隣接ノードを取得するクエリがスマートに記述できません。反対に、部分木検索が不可能に近い隣接リストモデルは、隣接する親子ノードを検索する一点に於いてのみその名に恥じぬパフォーマンスを発揮します。
このような現状に対して、次のような考え方があります。
隣接ノードの取得と部分木の取得が排反する事象で、単独のモデルでは両方をカバーするのが難しいのなら、それぞれの長所を合体させれば好い。
「好いとこ取り」と要約できますが、これは非常に合理的です。ツリー構造データを RDB で扱うモデルを実装した一部のライブラリでは、ひとつのモデルの中に次のふたつを含んだデザインになっているものがあります。
- 隣接リストモデルの親カラム
- 入れ子集合モデルの左右カラム
上記のふたつを合わせれば、部分木も隣接ノードも、検索効率が両方○になるというわけです。