モデルデザイン
Fettile Forest モデルでは、全く新しい発想で階層構造カラムが設計されています。
階層構造のマトリックス化
以下のツリー構造データを元にして図説します。
[A]
|
+---+---+
| |
[B] [C]
| |
+-+-+ +-+-+
| | | |
[D] [E] [F] [G]
|
+-+-+
| |
[H] [I]
(1) ツリー全体を以下のように変形します。
[A]
|
+-------+
| |
[B] [C]
| |
+---+ +---+
| | | |
[D] [E] [F] [G]
|
+---+
| |
[H] [I]
(2) ノードがタテにひとつだけになるよう、更に変形します。
[A]--+-----------+
| |
[B]--+---+ [C]--+---+
| | | |
[D] [E] [F] [G]--+---+
| |
[H] [I]
全体をグリッド平面に見立てて、ノードのある位置の XY 軸に附番します。
0 | [A]--+-----------+
| | |
1 | [B]--+---+ [C]--+---+
| | | | |
2 | [D] [E] [F] [G]--+---+
| | |
3 | [H] [I]
--+-------------------------------------
| 0 1 2 3 4 5 6 7 8
この図で、各ノードはユニークな XY 座標を持ちます。この XY 座標によりノードの階層構造位置を特定するのが、 FF モデルの骨子です。
附番された XY 座標は、次のように定義されます。
- X 軸
- QUEUE （序列）
- Y 軸
- DEPTH （深度）
FF モデルのテーブルは、複数のツリーを格納できます。その場合、 2番目以降の根ノードの QUEUE は、以前のツリーのノード数に応じて決まります。
DEPTH|
0 | [A]--+-----------+ [J]--+---------------+
| | | | |
1 | [B]--+---+ [C]--+---+ [K]--+ [L]--+
| | | | | | |
2 | [D] [E] [F] [G]--+---+ [M]--+---+ [N]
| | | | |
3 | [H] [I] [O] [P]
--+----------------------------------------------------------------------
| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 QUEUE
RDB テーブル設計
「序列」と「深度」を格納するカラムを階層構造カラムとして RDB テーブルに追加します。
| id | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| name | A | B | C | D | E | F | G | H | I |
| ff_queue | 0 | 1 | 4 | 2 | 3 | 5 | 6 | 7 | 8 |
| ff_depth | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 |
CREATE TABLE `ff_tables` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(225) DEFAULT NULL,
`ff_queue` int(11) NOT NULL,
`ff_depth` int(11) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;
INSERT INTO `ff_tables`
(`id`, `name`, `ff_queue`, `ff_depth`)
VALUES
(1, 'A', 0, 0), (2, 'B', 1, 1), (3, 'C', 4, 1),
(4, 'D', 2, 2), (5, 'E', 3, 2), (6, 'F', 5, 2),
(7, 'G', 6, 2), (8, 'H', 7, 3), (9, 'I', 8, 3)
;
ff_queue は、テーブル内の全ノードについてユニークでなければなりません。ただし、 ff_queue に UNIQUE KEY は指定できません。理由は、後述するノードの移動の際にそれがエラーを生じさせるからです。
QUEUE は、全ノードに一定の規則で振られたシリアルナンバーと考えられます。このことから、 FF モデルは「直列化ツリーモデル（ Serialized Tree Model ）」とも呼ばれます。
テーブルに付与するインデックス
FF モデルでは、基本的な検索クエリは総てインデックスが参照できます。そのために、テーブルには以下のようにインデックスを付与します。
CREATE TABLE `ff_tables` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`ff_depth` int(11) NOT NULL,
`ff_queue` int(11) NOT NULL,
PRIMARY KEY (`id`),
KEY `ff_queue_index` (`ff_queue`),
KEY `ff_depth_index` (`ff_depth`,`ff_queue`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;
ff_queue_index は、検索全般で使われます。 FF モデルの根幹となるインデックスです。
ff_depth_index は複合インデックスになっています。子孫ノード検索の際、サブクエリ内で「部分木の末尾ノード」を取得していますが、その検索速度のために使われます。
格納データからツリー構造データを復元する
ツリー構造データを RDB で扱うモデルには、ふたつの役割がありました。（第一章 第一節）
- ツリー構造データを RDB テーブルに格納する。
- 任意のノードについて、「部分木」や「親ノード」「子ノード」「祖先ノード」「子孫ノード」などの関連ノードを効率的に取得するクエリを記述する。
FF モデルで格納したデータからツリー構造を復元する手順を検証してみます。
(1) 保存された全ノードを、 QUEUE カラムと DEPTH カラムでグリッド平面上にマッピングします。
DEPTH|
|
0 | [A]
|
1 | [B] [C]
|
2 | [D] [E] [F] [G]
|
3 | [H] [I]
-----+-------------------------------------------
| 0 1 2 3 4 5 6 7 8 QUEUE
(2) 各ノードから「ひとつ上の深度」を左へ進み、最初に見つかったノードを親ノードとします。
DEPTH|
|
0 | [A]--+-----------+
| | |
1 | [B]--+---+ [C]--+---+
| | | | |
2 | [D] [E] [F] [G]--+---+
| | |
3 | [H] [I]
-----+-------------------------------------------
| 0 1 2 3 4 5 6 7 8 QUEUE
(3) 上図を変形すると、下図が得られます。
[A]
|
+---+---+
| |
[B] [C]
| |
+-+-+ +-+-+
| | | |
[D] [E] [F] [G]
|
+-+-+
| |
[H] [I]
これで、モデルデザインのひとつ目の条件である「 RDB テーブルに保存したデータからツリー構造を復元する」についての条件が満たされていることが分かりました。
ふたつ目の項目「効率的な検索クエリが書ける」については、次節「ノードの検索」で検証します。