从 SQLite DB 树表示中选择下一个（同级）和上一个（同级）

Question

我在 SQLite DB 中有以下示例树结构：

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;

我想我需要使用 WHERE NOT EXISTS 子句，但我不知道如何实现这一点。我应该提到的是，改变数据库结构不是一个选择。

预先感谢您的任何帮助。

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 顺序中的下一个节点。