Mysql query for linked list

Question

I use a table that implemented a singly linked list (id, parent). This implementation works well, except that recently, performance has become unbearable as my lists get longer, and I requested nodes individually.

I found a promising blog on how to request this in a single request. 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 

The only thing is that I'm not good enough at MySQL to even use it. The questions I have are the same as in the blog comments. how to set which entry / node to start? For example, if I wanted to start with id 3 in the example table. And how does he know when he gets to the end of the list and has to stop? Ive tried this and it just works forever (probably due to the misuse associated with the previous question).

Thanks.

Answer 1

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

To add boundaries, this option 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; 

Replace @start and @limit with the id first element and the maximum number of elements to extract, respectively. Please test it here .

---

Modeling such a data structure using a DBMS is probably a bad idea. Why not just use the index column? Listing becomes instant:

 SELECT * FROM list ORDER BY index_column ASC; 

Perhaps your list is intended to change often, but such queries should be fast enough if the list is not very 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;