Fetching связанного список в базе данных 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. У вас просто длинное, тощее дерево.

Существует несколько решений для хранения и извлечения такой структуры данных из РСУБД. См некоторые из следующих вопросов:

• «What is the most efficient/elegant way to parse a flat table into a tree?»
• «Is it possible to make a recursive SQL query ?»

---

Так вы говорите, что вы хотите, чтобы ограничить «глубину», возвращаемый запросом, вы можете достичь этого при запросе списка таким образом:

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); 

Это будет p erform, как меласса, и результат вернется все в одну строку (по связанному списку), но вы получите результат.

Answer 2

Это меньше решение и более обходной путь, но для линейного списка (а не дерева, упомянутого Биллом Карвином) было бы более эффективно использовать столбец сортировки в вашем списке. Например:

TABLE `schema`.`my_table` (
    `id` INT NOT NULL PRIMARY KEY, 
    `order` INT, 
    data .., 
    INDEX `ix_order` (`sort_order` ASC) 
); 

Тогда:

SELECT * FROM `schema`.`my_table` ORDER BY `order`; 

Это имеет тот недостаток, что более медленные вставок (вы должны изменить все упорядоченные элементы мимо точки вставки), но должны быть быстрыми для поиска, так как столбец заказа индексируются.

Answer 3

Если вы пытаетесь избежать, у вас есть несколько запросов (по одному для каждого узла), и вы можете добавлять столбцы, тогда у вас может быть новый столбец, который ссылается на корневой узел. Таким образом, вы можете получить все данные сразу по корневому идентификатору, но вам все равно придется сортировать список (или дерево) на стороне клиента.

Так это пример вы бы:

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

Конечно недостатком этого, в отличие от традиционных связанных списков или деревьев является то, что корень не может быть изменена без написания на порядок величины O (n) где n - количество узлов. Это связано с тем, что вам придется обновлять идентификатор корня для каждого узла. К счастью, хотя вы всегда должны быть в состоянии сделать это в одном запросе на обновление, если вы не разделите список/дерево посередине.