Nested Set Model
When considering each node as a circle, Nested Set Model represent a parent-child relationship by a nested circles. It was proposed by Mr. Joe Celko (United State of America) in 2004. In a lot of framework, Nested Set Model has been used as a model to storing hierarchical data in a RDB. (until Dec 2024)
Model Design
I am going to express the following tree structure data indicated in Nested Set Model. [A], [B], ... indicated in figure means nodes.
[A]
|
+---+---+
| |
[B] [C]
| |
+-+-+ +-+-+
| | | |
[D] [E] [F] [G]
|
+-+-+
| |
[H] [I]
Firstly, pretend serial number to the left and right of each node as follows. These left and right columns are as a hierarchical structure column in the Nested Set Model.
[1 A 18]
|
+-------+--------+
| |
[2 B 7] [8 C 17]
| |
+---+---+ +----+----+
| | | |
[3 D 4] [5 E 6] [9 F 10] [11 G 16]
|
+----+----+
| |
[12 H 13] [14 I 15] Rule of Numbering
Gives a left and right number by repeating the following steps from the root node, as shown in the figure above.
- If current node has no left number, give a number in left of current node.
- If the current node has a child node that has no left number, move to the left-most child node. And then the process returns to first step.
- If the current node has no child node which has no left number, gives current node right number and moves to parent node. And then the process returns to first step.
- Exits if the current node has no parent node.
Nesting of the node is indicated as shown in the figure below. The left and right numbers are lined from left in ascending order.
You can see that the left and right numbers of each node is within the range of the left and right of its parent node. For example, the left and right number of [G] is (11, 16). And the left and right number of [H] and [I] is within the range of [G]. Therefore, can determine [H] and [I] to be a descendant node of [G].
I am going to consider the table that has columns of id and name of each node, as a minimum of information about the node. Because of the table has no columns for hierarchical structure, can not restore tree data from the records in the table.
| id | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| name | A | B | C | D | E | F | G | H | I |
Add two columns to RDB table, for storing the left and right number. The two columns to be referred to as "left and right columns". Left and right columns has functions as hierarchical structure column and search efficiency column.
| id | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| name | A | B | C | D | E | F | G | H | I |
| tree_left | 1 | 2 | 8 | 3 | 5 | 9 | 11 | 12 | 14 |
| tree_right | 18 | 7 | 17 | 4 | 6 | 10 | 16 | 13 | 15 |
CREATE TABLE `nested_set_models` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(225) DEFAULT NULL,
`tree_left` int(11) NOT NULL,
`tree_right` int(11) NOT NULL,
PRIMARY KEY (`id`),
KEY `left_index` (`tree_left`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;
INSERT INTO `nested_set_models`
(`id`, `name`, `tree_left`, `tree_right`)
VALUES
(1, 'A', 1, 18), (2, 'B', 2, 7), (3, 'C', 8, 17),
(4, 'D', 3, 4), (5, 'E', 5, 6), (6, 'F', 9, 10),
(7, 'G', 11, 16), (8, 'H', 12, 13), (9, 'I', 14, 15);