ツリーモデルのテーブル設計に便利なNested Set Model（入れ子集合モデル）

2010/02/26 18:56Update

複数階層の親子関係を持ついわゆるツリー関係をテーブル化（モデル化）にする際、便利なNested Set Modelについて。

ツリー関係例

ファイルシステムのフォルダ（Folder）とファイル（File）はその一例である。
Folder（ID、親フォルダID、フォルダ名）
File（ID、親フォルダID、ファイル名）

このままデータベースにテーブルに持っていくと、検索に扱いづらいところがあります。

ツリー関係をテーブル化する際の問題点

例えば、あるフォルダにあるすべてのファイル及びサブフォルダにあるファイルを検索しようとすると、再帰参照することになる。これはデータベースに多くのクエストを発行し、負荷に掛かる。

そこで、Nested Set Model（入れ子集合モデル）という設計手法がある。
Nested Set Modelは、テーブルにint型のlftとrgtカラムを追加する。

Folder（ID、親フォルダID、フォルダ名、lft、rgt）
File（ID、親フォルダID、ファイル名、lft、rgt）

lft、rgtの値の設定ルールは次のようになる：

例えば、
次のようなフォルダ階層と考えると
Folder1
∟File1
∟Folder2
　∟File21
　∟File22
∟Folder3
　∟File31
∟Folder4
　∟File41
　
Nested Set Modelはこのように表現する：
lft=1 (Folder1
    lft=2 (File1) rgt=3
    lft=4 (Folder2
        lft=5 (File21) rgt=6
        lft=7 (File22) rgt=8
    ) rgt=9
    lft=10 (Folder3
        lft=11 (File31) rgt=12
    ) rgt=13
    lft=14 (Folder4
        lft=15 (File41) rgt=16
    ) rgt=17
) rgt=18

Folder1.lft = 1    .rgt = 18
    File1  .lft = 2    .rgt = 3
    Folder2.lft = 4    .rgt = 9
        File21 .lft = 5    .rgt = 6
        File22 .lft = 7    .rgt = 8
    Folder3.lft = 10    .rgt = 13
        File31 .lft = 11    .rgt = 12
    Folder4.lft = 14    .rgt = 17
        File41 .lft = 15    .rgt = 16

1(    2()3    4(    5()6    7()8    )9    10(    11()12    )13    14(    15()16    )17    )18

即ち、
これがあれば、どんな複雑な階層でも簡単にデータを検索できる
例えば、
Folder2とそのサブフォルダにあるすべてのサブファイルを検索する例：

SELECT file.* FROM Folder folder, File file
WHERE folder.name = 'Folder2'
AND file.lft > folder.lft
AND file.rgt < folder.rgt

lftとrgtの値の設定は　テーブルの挿入や更新・削除時に　プロシージャや　プログラムの中に行えばよい。