Реализация иерархической структуры данных в базе данных - PullRequest
Новая
       35

Реализация иерархической структуры данных в базе данных

12 голосов
/ 13 февраля 2009

Я знаю, что есть два подхода: список смежности и вложенное дерево. Говорят, что список смежности может стать медленным для использования из-за многочисленных запросов. Но я не знаю реальных цифр для этого. Сайт, который я делаю, будет иметь около 200 страниц. Обход для создания (например) карты сайта займет больше времени, чем примерно 0,3 секунды?

Запуск на MySQL (innoDB) со стеком LAMP.

Я бы предпочел реализовать смежность, если это возможно, из-за более упрощенного дизайна.

Спасибо.

Ответы [ 6 ]

14 голосов
/ 13 февраля 2009

Есть больше вариантов, чем просто два, которые вы упомянули. Есть:

  • Список смежности ("parent_id", который используют почти все)
  • Вложенные множества
  • Перечисление пути
  • Таблица закрытия (отношение смежности)

См. Мой ответ на " Какой самый эффективный / элегантный способ разбить плоский стол на дерево? "

Или пару книг:

4 голосов
/ 13 февраля 2009

Статья Управление иерархическими данными в MySQL подробно описывает это.

Я бы порекомендовал метод "вложенного множества", поскольку он позволяет получить все дерево (и его дочерние элементы) в одном запросе. В основном чтения дешевы, но записи дороги, потому что все дерево должно быть сбалансировано. Но в тех случаях, когда вы читаете 99%, это вполне оправдано.

3 голосов
/ 13 февраля 2009

Наивный подход к синтаксическому анализу списка смежности требует большого количества запросов, а для больших списков может потребоваться значительное количество времени для наращивания памяти. Для справки, наивный подход, на который я ссылаюсь, может быть кратко изложен следующим образом: выбрать все элементы без родителей, затем для каждого элемента рекурсивно получить его дочерние элементы. Этот подход требует n + 1 запросов к базе данных.

Я использовал следующий подход для построения списка смежности с 1 запросом. Выберите все элементы из базы данных. Перенести все элементы в массив, проиндексированный по их ключу. Обойдите массив и назначьте ссылку из родительского объекта каждому из его дочерних элементов. Пройдите через массив еще раз и удалите все дочерние объекты, оставив только объекты корневого уровня.

Поскольку вы упомянули стек LAMP, код PHP для этого выглядит примерно так: 

<?php
// Assumes $src is the array if items from the database.
$tmp = array();

// Traverse the array and index it by id, ensuing each item has an empty array of children.
foreach ($src as $item) {
  $item['children'] = array();
  $tmp[$item['id']] = $item;
}

// Now traverse the array a second time and link children to their parents.
foreach ($tmp as $id => $item) {
  if ($item['parent_id'] != 0 || $item['parent_id'] !== NULL) {
    $tmp[$item['parent_id']]['children'][$id] = &$tmp[$id];
  }
}

// Finally create an array with just root level items.
$tree = array();
foreach ($tmp as $id => $item) {
  if ($item['parent_id'] == 0 || $item['parent_id'] === NULL) {
    $tree[$id] = $item;
  }
}

// $tree now contains our adjacency list in tree form.
?>

Обратите внимание, этот код предназначен для иллюстрации методики построения списка смежности из одного запроса к базе данных. Вероятно, он может быть оптимизирован для меньшего потребления памяти и т. Д. Он также не был протестирован.

Jim

2 голосов
/ 13 февраля 2009

Для полноты: Oracle имеет операторы START_WITH и CONNECT_BY: см. Этот документ Иерархические запросы .

2 голосов
/ 13 февраля 2009

Другой подход называется «вложенным множеством», а не «вложенным деревом».

В любом случае, хорошая вещь о карте сайта в том, что вы знаете ее максимальную глубину. Я думаю, что проблема с моделью смежности заключается в том, что соответствующий SQL работает на одном уровне за раз, поэтому, если у вас есть «n» уровней, вам нужен цикл из «n» операторов SQL ... но я думаю (I я не уверен), что если вы заранее знаете максимальное значение «n», вы можете закодировать соответствующий SQL с фиксированным числом множественных уровней.

0,3 секунды для меня звучат как очень долгое время, чтобы вычислить 200 страниц, так что, вероятно, все в порядке.

Также карта сайта обновляется не очень часто; поэтому, даже если для извлечения из SQL требуется много времени, вы, вероятно, можете кэшировать извлеченное / вычисленное дерево в ОЗУ.

В качестве альтернативы, вместо того, чтобы беспокоиться о SQL для построения дерева, вы можете просто сохранить его как можно проще (в виде списка смежности), извлечь его из базы данных в виде простого набора строк и построить дерево в ОЗУ ( использование циклов в вашем языке программирования высокого уровня) вместо использования циклов в SQL для построения дерева с помощью операторов SQL.

2 голосов
/ 13 февраля 2009
...