To Add Node
When add a new node as a child of an existing node, need to shift the QUEUE of all nodes on the right side of the existing nodes. This is similar to the problem contained in Nested Set Model.
DEPTH|
|
0 | [A]--+-----------+
| | |
1 | [B]--+---+ [C]--+---+
| | | | |
2 | [D] [E] [F] [G]--+---+
| | |
3 | [H] [I]
-----+-------------------------------------------
| 0 1 2 3 4 5 6 7 8 QUEUE
In the figure above, consider to add a new node [J] as a child of the node [E]. Node [J] will be added to the position shown in the following figure. However, can not supply numbering the QUEUE to [J] in this state.
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
QUEUE of [E] is 3. After shifted one by one QUEUE to the right than 3, can supply number 4 as QUEUE to node [J].
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
DEPTH of the newly added [J] is "(DEPTH of [E]) + 1". It is a self-evident. QUEUE and DEPTH for new node since has been determined, can create INSERT statement for adding node [J]. the procedure in SQL as follows.
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;
This is in basic additional processing primitive FF model. If RDB table has several hundreds of million, the cost of shifting the QUEUE will be huge. For this reason, I implemented the devise in order to reduce the additional cost in my libraries for CakePHP and Ruby on Rails.
To Add Root Node
In case to add a root node, DEPTH of the added node is zero. When add to the back of the existing records, can cut off the cost of shifting the 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
Damage possible of the referential integrity.
When use the transaction for adding new node, damage possible of the referential integrity of the tree structure column is very low.