ノード追加

新しいノードを既存ノードの子として追加する際、既存ノードの右側にある全ノードの QUEUE をずらす必要があります。これは、「入れ子集合モデル」抱えている問題と類似のものです。

原始的 FFモデルに於けるノード追加方法

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


mysql> INSERT INTO ff_queue (name, ff_depth, ff_queue)
  VALUES ('J', 0, 9)
;

リンク