mysql 查询链表

2022-01-01 00:00:00 linked-list sql mysql

我使用的表已经实现了单链表(id、父).这个实现一直运行良好，但最近性能变得难以忍受，因为我的列表越来越长，而且我一直在单独查询节点.

I'm using a table that has implemented a single-linked list (id, parent). This implementation has been working well except recently performance has become unbearable since my lists are getting long and I've been querying nodes individually.

我发现了一个很有前途的博客，介绍了如何在单个查询中进行查询.http://explainextended.com/2009/03/25/sorting-lists/

I found a promising blog on how to query this in a single query. http://explainextended.com/2009/03/25/sorting-lists/

SELECT  @r AS _parent,
        @r := (
        SELECT  id
        FROM    t_list
        WHERE   parent = _parent
        ) AS id
FROM    (
        SELECT  @r := 0
        ) vars,
        t_list

唯一的问题是我对 MySQL 不够了解甚至无法使用它.我的问题与我在博客评论中发布的问题相同.如何设置从哪个记录/节点开始?就像我想从示例表中的 id 3 开始.它如何知道何时到达列表末尾并应该停止?我试过了，它永远运行(可能是由于与前一个问题相关的不当使用).

Only thing is I'm not MySQL savvy enough to even use it. Questions I have are same as I posted on the blogs comments. how to set which record/node to start from? Like if I wanted to start from id 3 in the example table. And how does it know when it hits the end of the list and should stop? I’ve tried it out and it just runs forever (likely due to improper use related to the former question).

谢谢.

推荐答案

查询的工作原理是遍历 t_list 表(最后一行).对于该表中的每一行，SELECT 子句中的子查询重新查询该表，搜索当前行的子行(WHERE parent = _parent -- 但_parent 是 @r 的别名).在每次迭代中，孩子的 id 被分配给 @r 变量.

The query works by iterating over the t_list table (the last line). For each row in this table, the sub-query in the SELECT clause re-queries the table, searching for the current row's child (WHERE parent = _parent -- but _parent is an alias for @r). At each iteration, the child's id is assigned to the @r variable.

要添加边界，此变体应该可以解决问题:

To add boundaries, this variation should do the trick:

SELECT * FROM (
    SELECT
        @r AS _parent,
        @r := (
            SELECT id
            FROM t_list
            WHERE
                ( @c = 0 AND _parent IS NULL AND parent IS NULL ) -- special case if the first item is the root
                OR (parent = _parent)
        ) AS id,
        @c := @c + 1 AS rank
    FROM (
        SELECT @c := 0, @r := parent FROM t_list WHERE id = @start
    ) AS ini,
    (
        SELECT id FROM t_list LIMIT @limit
    ) AS lim
) AS tmp WHERE id IS NOT NULL;

将 @start 和 @limit 分别替换为第一项的 id 和要检索的最大项数.请在这里测试.

Replace @start and @limit with the id of the first item, and the maximum number of items to retrieve, respectively. Please test it here.

用 RDBMS 对这样的数据结构进行建模可能完全是个坏主意.为什么不只使用索引"列?立即获取列表:

Modeling such a data structure with a RDBMS is probably a bad idea altogether. Why not just use an "index" column? Getting the list then becomes instant:

SELECT * FROM list ORDER BY index_column ASC;

也许您的列表应该经常更改，但除非列表变得非常大，否则像这样的查询应该相当快:

Maybe your list is meant to change frequently, but queries like this should be fairly fast unless the list grows really large:

-- insert an element at position X 
UPDATE list SET index_column = index_column +1 WHERE index_column > X ORDER BY index_column DESC;
INSERT INTO list VALUE (some_value, X);

-- delete an element at position X 
DELETE FROM list WHERE index_column = X;
UPDATE list SET index_column = index_column -1 WHERE index_column > X ORDER BY index_column ASC;

相关文章