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

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

Работа с MySQL (innoDB) с использованием стека LAMP.

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

Спасибо.

Ответы

Ответ 1

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

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

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

Или несколько книг:

Ответ 2

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

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

Ответ 3

Наивный подход к разбору списка смежности требует большого количества запросов, а для больших списков может потребоваться значительное количество времени для создания в памяти. Для справки, наивный подход, к которому я имею в виду, можно суммировать как: Выбрать все элементы без родителя, Затем для каждого элемента рекурсивно получить его детьми. Для этого подхода требуется 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.
?>

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

Джим

Ответ 5

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

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

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

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

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