Nested Sets дерево - PHP

Не понимаю, как вычисляются ключи left и right, я никак понять не могу?

Вот допустим, нужно такое дерево:

Программирование
-PHP
-JS
-Python

Всего 4 узла. В первом правом ключе, будет произведение суммы всех узлов * на 2.

1 узел

id = 1, level = 1, left = 1, right = 8

2 узел

id =2 , level =2 , left = ? , right = ? Вот здесь я вообще не понимаю, как вычислять?

Смотрю на картинку и не понимаю

 

В общем вычислять ключи надо по кругу

 

Разобрался с добавлением подкатегории, поправьте меня, если я где-то ошибся.

Вот такая структура, фото есть во вложении

Код (Text):

1. CREATE table language (
2.     id         serial,
3.     left_key   INTEGER       NOT NULL,
4.     right_key  INTEGER       NOT NULL,
5.     level      INTEGER       NOT NULL DEFAULT 0,
6.     name VARCHAR(50) NOT NULL
7. );
8.  
9.  
10. INSERT INTO language (id, level, left_key, right_key, name) VALUES
11.     (1, 1, 1, 12, 'Языки'),
12.     (2, 2, 2, 5, 'PHP'),
13.     (3, 3, 3, 4, 'PHP7'),
14.     (4, 2, 6, 9, 'JS'),
15.     (5, 3, 7, 8, 'React'),
16.     (6, 2, 10, 11, 'HTML');

Вывод древовидного меню, без рекурсии и циклов

Код (Text):

1. SELECT
2.     repeat('.', language.level*2) || name,
3.     level
4. FROM
5.     language
6. ORDER BY
7.     left_key;

Вот так должно быть

Код (Text):

1. postgres-#     left_key;
2.   ?column?   | level
3. -------------+-------
4. ..Языки     |     1
5. ....PHP     |     2
6. ......PHP7  |     3
7. ....JS      |     2
8. ......React |     3
9. ....HTML    |     2
10. (6 rows)

Добавляю новую категорию Laravel в PHP.

Код (Text):

1. postgres=# select * FROM language;
2. id | left_key | right_key | level | name
3. ----+----------+-----------+-------+-------
4.   1 |        1 |        12 |     1 | Языки
5.   2 |        2 |         5 |     2 | PHP
6.   3 |        3 |         4 |     3 | PHP7
7.   4 |        6 |         9 |     2 | JS
8.   5 |        7 |         8 |     3 | React
9.   6 |       10 |        11 |     2 | HTML

Для этого узнаю правый ключ у той категории, в которую добавляю и всем
листочкам (у которых левый ключ больше) увеличиваю оба ключа на 2;

Код (Text):

1. UPDATE language
2.     SET
3.         left_key = left_key + 2,
4.         right_key = right_key + 2
5.     WHERE
6.         left_key > 5;

Проверяю, что получилось

Код (Text):

1. postgres=# select * FROM language;
2. id | left_key | right_key | level | name
3. ----+----------+-----------+-------+-------
4.   1 |        1 |        12 |     1 | Языки
5.   2 |        2 |         5 |     2 | PHP
6.   3 |        3 |         4 |     3 | PHP7
7.   4 |        8 |        11 |     2 | JS
8.   5 |        9 |        10 |     3 | React
9.   6 |       12 |        13 |     2 | HTML

Теперь обновляю родителя:

Код (Text):

1. UPDATE language
2.     SET right_key = right_key + 2
3.     WHERE
4.         right_key >= 5 AND
5.         left_key < 5;

Код (Text):

1. postgres=# select * FROM language;
2. id | left_key | right_key | level | name
3. ----+----------+-----------+-------+-------
4.   3 |        3 |         4 |     3 | PHP7
5.   4 |        8 |        11 |     2 | JS
6.   5 |        9 |        10 |     3 | React
7.   6 |       12 |        13 |     2 | HTML
8.   1 |        1 |        14 |     1 | Языки
9.   2 |        2 |         7 |     2 | PHP

Добавляю подкатегорию с ключом 5

Код (Text):

1. INSERT INTO language (level, left_key, right_key, name) VALUES
2.     (3, 5, 5+1, 'Laravel');

Вывожу и вижу, что всё работает, как надо

Код (Text):

1.    ?column?    | level
2. ---------------+-------
3. ..Языки       |     1
4. ....PHP       |     2
5. ......PHP7    |     3
6. ......Laravel |     3
7. ....JS        |     2
8. ......React   |     3
9. ....HTML      |     2
10. (7 rows)

Ищу дубликаты строк, если они есть, значит где-то произошла ошибка.

Код (Text):

1. SELECT
2.     left_key, right_key, COUNT(*)
3. FROM
4.     language
5. GROUP BY
6.     left_key, right_key
7. HAVING
8.     COUNT(*) > 1;

 

Удаляю добавленный узел "Laravel"

Узнаю, что у него левый ключ 5, а правый 6

Код (Text):

1. DELETE FROM language
2.     WHERE
3.         left_key >= 5 AND
4.         right_key <= 6;

Обновление родительской ветки (PHP)

Код (Text):

1. UPDATE language
2.     SET
3.         right_key = right_key - ( 6 - 5 + 1)
4.     WHERE
5.         right_key > 6 AND
6.         left_key < 5;

Обновление последующих узлов

Код (Text):

1. UPDATE language
2.     SET
3.         left_key = left_key - ( 6 - 5 + 1 ),
4.         right_key = right_key - (6 - 5   + 1 )
5.     WHERE
6.         left_key > 5;

Если всё правильно сделано, то все ключи, должны сбросится в первоначальные значения, то есть должны быть такими же, как и при первом заполнении таблицы.