ノードの追加
新しいノードを既存ノードの子として追加する際、その既存ノードの右側にある全ノードの QUEUE をずらす必要があります。これは、「入れ子集合モデル」抱えている問題と類似のものです。
DEPTH|
|
0 | [A]--+-----------+
| | |
1 | [B]--+---+ [C]--+---+
| | | | |
2 | [D] [E] [F] [G]--+---+
| | |
3 | [H] [I]
-----+-------------------------------------------
| 0 1 2 3 4 5 6 7 8 QUEUE
上図で、新しいノード [J] をノード [E] の子として追加する場合を考えます。 [J] は下図の位置に追加されますが、このままでは [J] に QUEUE を附番できません。
DEPTH|
|
0 | [A]--+---------------+
| | |
1 | [B]--+---+ [C]--+---+
| | | | |
2 | [D] [E]--+ [F] [G]--+---+
| | | |
3 | [J] [H] [I]
-----+-------------------------------------------------
| 0 1 2 3 (?) 4 5 6 7 8 QUEUE
[E] の QUEUE は 3です。 3より右にある QUEUE をひとつずつずらせば、 [J] に 4を割り当てられます。
DEPTH|
|
0 | [A]--+---------------+
| | |
1 | [B]--+---+ [C]--+---+
| | | | |
2 | [D] [E]--+ [F] [G]--+---+
| | | |
3 | [J] [H] [I]
-----+-------------------------------------------------
| 0 1 2 3 (4) 5 6 7 8 9 QUEUE
新規追加される [J] の DEPTH が "[E] 深度 + 1" なのは自明です。これで [J] の [DEPTH, QUEUE] が決定したので、 INSERT 文が記述できます。この手順を SQL で表現すると、以下のようになります。
mysql> BEGIN;
mysql> UPDATE ff_tables
SET ff_queue = ff_queue + 1
WHERE ff_queue > 3
;
mysql> INSERT INTO ff_queue (name, ff_depth, ff_queue)
VALUES ('J', 3, 4)
;
mysql> COMMIT;
これは、原始的 FF モデルに於ける基本的な追加処理です。原始モデルでは、レコード数が数億に及ぶテーブルの場合、 QUEUE をずらすコストが膨大になります。このコストを回避するために、私が作成したライブラリでは、追加コストを抑えるための工夫が実装されています。
根ノードの追加
根ノードを追加する場合、追加されるノードの DEPTH は 0です。既存のレコードの後ろに追加すれば、 QUEUE をずらすコストは発生しません。
DEPTH|
|
0 | [A]--+-----------+ [J]
| | |
1 | [B]--+---+ [C]--+---+
| | | | |
2 | [D] [E] [F] [G]--+---+
| | |
3 | [H] [I]
-----+------------------------------------------------
| 0 1 2 3 4 5 6 7 8 9 QUEUE
参照整合性の破損可能性
トランザクションを使って UPDATE と INSERT を実行している限り、保存時にツリー構造カラムの参照整合性が破損することはありません。