获取MySQL数据库中的链表

Question

我有一个具有这种结构的MySQL数据库表:

table
    id INT NOT NULL PRIMARY KEY
    data ..
    next_id INT NULL

我需要按链表顺序获取数据.例如,给定这些数据:

 id | next_id
----+---------
  1 |       2
  2 |       4
  3 |       9
  4 |       3
  9 |    NULL

我需要按顺序获取id = 1,2,4,3,9的行.如何使用数据库查询执行此操作？(我可以在客户端完成.我很好奇是否可以在数据库端完成.因此,说这是不可能的(没有足够的证明)).

有一个终止点也是很好的(例如,在10次提取后停止,或者当行上的某些条件变为真时),但这不是必需的(可以在客户端完成).我(希望我)不需要检查循环引用.

Answer 1

某些品牌的数据库(例如Oracle,Microsoft SQL Server)支持额外的SQL语法来运行"递归查询",但MySQL不支持任何此类解决方案.

您描述的问题与表示SQL数据库中的树结构相同.你只有一棵长而瘦的树.

有几种解决方案用于从RDBMS存储和获取这种数据结构.请参阅以下一些问题:

• " 将平台解析成树的最有效/最优雅的方法是什么？ "
• " 是否有可能进行递归SQL查询？ "

既然您提到要限制查询返回的"深度",则可以通过以下方式查询列表来实现此目的:

SELECT * FROM mytable t1
 LEFT JOIN mytable t2 ON (t1.next_id = t2.id)
 LEFT JOIN mytable t3 ON (t2.next_id = t3.id)
 LEFT JOIN mytable t4 ON (t3.next_id = t4.id)
 LEFT JOIN mytable t5 ON (t4.next_id = t5.id)
 LEFT JOIN mytable t6 ON (t5.next_id = t6.id)
 LEFT JOIN mytable t7 ON (t6.next_id = t7.id)
 LEFT JOIN mytable t8 ON (t7.next_id = t8.id)
 LEFT JOIN mytable t9 ON (t8.next_id = t9.id)
 LEFT JOIN mytable t10 ON (t9.next_id = t10.id);

它的表现就像糖蜜一样,结果会在一行(每个链表)返回,但你会得到结果.

Answer 2

如果您要避免的是有多个查询（每个节点一个）并且您能够添加列，那么您可以拥有一个链接到根节点的新列。这样您就可以通过根 ID 一次性提取所有数据，但您仍然需要在客户端对列表（或树）进行排序。

所以在这个例子中你会有：

 id | next_id | root_id
----+---------+---------
  1 |       2 |       1
  2 |       4 |       1
  3 |       9 |       1
  4 |       3 |       1
  9 |    NULL |       1

当然，与传统的链表或树相比，这种方法的缺点是如果不写入 O(n) 的数量级，则根无法更改，其中 n 是节点数。这是因为您必须更新每个节点的根 ID。幸运的是，除非您在中间划分列表/树，否则您应该始终能够在单个更新查询中执行此操作。