Извлечение связанного списка в базе данных MySQL - PullRequest
Новая
       21

Извлечение связанного списка в базе данных MySQL

7 голосов
/ 23 марта 2009

У меня есть таблица базы данных 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 выборок или когда какое-либо условие в строке становится истинным), но это не является обязательным требованием (может быть выполнено на стороне клиента). Я (надеюсь, мне) не нужно проверять циклические ссылки.

Ответы [ 3 ]

5 голосов
/ 23 марта 2009

Некоторые базы данных (например, Oracle, Microsoft SQL Server) поддерживают дополнительный синтаксис SQL для выполнения «рекурсивных запросов», но MySQL не поддерживает ни одно из таких решений.

Проблема, которую вы описываете, аналогична представлению древовидной структуры в базе данных 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);

Он будет работать как патока, и результат будет возвращаться в одном ряду (для каждого связанного списка), но вы получите результат.

4 голосов
/ 31 августа 2010

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

Итак, в этом примере вы должны иметь: 

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

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

2 голосов
/ 13 августа 2010

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

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

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

...