Fertile Forest Model (7/n) ノード追加

# ノード追加

新しいノードを既存ノードの子として追加する際、既存ノードの右側にある全ノードの 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 で表現すると、以下のようになります。

``` 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 をずらすコストが膨大になります。

このコストを回避するために、私が作成したライブラリでは、追加コストを抑えるための工夫が実装されています。回避方法の全容をここで記すのは冗長なので、割愛します。詳細が知りたい方は拙作のライブラリを解読してみて下さい。

- [Fertile Forest Model for Plugin of CakePHP 3.x](https://packagist.org/packages/stew-eucen/fertile-forest)
- [Fertile Forest Model for RailsGem](https://rubygems.org/gems/fertile_forest)

## 根ノードの追加

根ノードを追加する場合、追加されるノードの 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
```

``` SQL

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

# リンク

- [ツリー構造データをRDBで扱うための第五のモデル](http://qiita.com/StewEucen/items/e0487c39285a9d6b7863)
- [RDB に於けるツリー構造データ (1)](http://qiita.com/StewEucen/items/18a1703353c735258a8a)
- [RDB に於けるツリー構造データ (2)](http://qiita.com/StewEucen/items/e5895d9f09beb16c61fd)
- [モデルデザイン](http://qiita.com/StewEucen/items/b4840343c22cea11ec26)
- [ノード検索＜祖先ノード系＞](http://qiita.com/StewEucen/items/632bddd683d77d1cf176)
- [ノード検索＜子孫ノード系＞](http://qiita.com/StewEucen/items/44901b69e2a061e0bc0a)
- [ノード検索＜親戚ノード系＞](http://qiita.com/StewEucen/items/22ba49ab8e591c663c84)
- ノード追加
- [ノード移動](http://qiita.com/StewEucen/items/bfb2f84d66929c0c4747)