Выберите следующий (брат) и предыдущий (брат) из представления дерева БД SQLite

Question

В базе данных SQLite есть следующая примерная древовидная структура:

id | idparent | order
1    -1         0
2     1         0
3     2         0
4     1         1

Что представляет собой следующее дерево:

1
|- 2
|  |- 3
|- 4

И я хотел бы создать оператор select, чтобы получить все узлы следующего, предыдущего, следующего родного брата и предыдущего родного брата. Такое утверждение вернулось бы из предыдущего примера:

id | idparent | next | previous | nextsibling | previoussibling
1    -1         2      NULL       NULL          NULL
2     1         3      1          4             NULL
3     2         4      2          NULL          NULL
4     1         NULL   3          NULL          2

Я могу получить следующее и предыдущее, но я застрял со следующим и предыдущим:

SELECT node.id, node.idparent,
??? AS next
??? AS previous,
(SELECT id FROM nodes WHERE idparent = node.idparent AND `order` > node.`order` LIMIT 1) AS nextsibbling,
(SELECT id FROM nodes WHERE idparent = node.idparent AND `order` < node.`order` LIMIT 1) AS previoussibbling
FROM nodes node;

Полагаю, мне нужно использовать предложение "ГДЕ НЕ СУЩЕСТВУЕТ", но я не могу понять, как мне этого добиться. Следует отметить, что изменение структуры БД не является вариантом.

Заранее спасибо за любую помощь.

Answer 1

Ваша схема (так называемая «модель списка смежности») довольно ограничена с точки зрения того, какие операции она поддерживает. Вместо этого попробуйте режим вложенного набора : хранить границы для каждого узла, а не для родительского узла. Узел спускается из всех узлов, где родительские границы содержат дочерние. Границы также дают глубину первого обхода дерева, где нижняя граница дает, когда узел входит, и верхняя граница дает, когда узел выходит. Таким образом, сортировка узлов по левой границе дает обход по предварительному порядку, а сортировка по праву дает обход по порядку.

CREATE TABLE `hier` (
  `id` int(11) PRIMARY KEY AUTO_INCREMENT,
  `left` int(11) NOT NULL,
  `right` int(11) NOT NULL,
  `data` varchar(128),
  INDEX `bounds` (`left`,`right`),
  INDEX `sdnuob` (`right`, `left`)
);

INSERT INTO HIER (id, `left`, `right`, data) 
   VALUES
 (1, 1, 8, 'foo'),
 (2, 2, 5, 'mane'), 
 (3, 3, 4, 'padme'), 
 (4, 6, 7, 'hum')
;

SELECT h.id AS node,
    p.id AS prev, p.`left` AS p_l, n.id AS `next`, n.`left` AS n_l,
    ps.id AS prevSibling, ns.id AS nextSibling
  FROM hier AS h
    LEFT JOIN hier AS p ON h.`left` > p.`left`
    LEFT JOIN hier AS pb ON h.`left` > pb.`left`
    LEFT JOIN hier AS n ON h.`left`< n.`left`
    LEFT JOIN hier AS nb ON h.`left`< nb.`left`
    LEFT JOIN hier AS ps ON h.`left` = ps.`right`+1
    LEFT JOIN hier AS ns ON h.`right`= ns.`left`-1
  GROUP BY node, prevSibling, nextSibling, p.`left`, n.`left`
  HAVING (p.`left` IS NULL OR p.`left` = MAX(pb.`left`))
     AND (n.`left` IS NULL OR n.`left` = MIN(nb.`left`))
;

Результат:

+------+------+------+------+------+-------------+-------------+
| node | prev | p_l  | next | n_l  | prevSibling | nextSibling |
+------+------+------+------+------+-------------+-------------+
|    1 | NULL | NULL |    2 |    2 |        NULL |        NULL |
|    2 |    1 |    1 |    3 |    3 |        NULL |           4 |
|    3 |    2 |    2 |    4 |    6 |        NULL |        NULL |
|    4 |    3 |    3 | NULL | NULL |           2 |        NULL |
+------+------+------+------+------+-------------+-------------+

Если вам действительно нужно найти родителя (или глубину) узла, вы можете использовать представление или технику, примененную в представлении к запросу:

CREATE VIEW hier_depth AS 
SELECT c.*, p.id AS parent, p.`left` AS p_left, COUNT(a.id) AS depth
  FROM hier AS c
    LEFT JOIN hier AS p ON p.`left` < c.`left` AND c.`right` < p.`right`
    LEFT JOIN hier AS a ON a.`left` < c.`left` AND c.`right` < a.`right`
  GROUP BY c.id, parent
  HAVING p.`left` IS NULL OR p.`left` = MAX(a.left)
;

Answer 2

Я не думаю, что ваша схема поддерживает запрос next. IIUC, вам может потребоваться пройти несколько уровней, чтобы определить следующий узел.

Я рекомендую добавить столбец path, который принимает в качестве значений пути, разделенные двоеточиями, например 1:2:3 или 1:4. Следующий узел будет следующим в порядке path.