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

Существует больше опций, чем просто два, которые Вы упоминаете. Существуют:

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

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

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

• "Деревья и иерархии в SQL для присяжных острословов" Joe Celko.
• "Шаблоны разработки SQL" Vadim Tropashko.

Статья Managing Hierarchical Data в MySQL входит в детали об этом.

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

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

Вот несколько вопросов, которые могли бы помочь Вам:

SQL, как сохранить и переместиться по иерархиям

Который является лучшей схемой базы данных для моей навигации

Для completeneness: Oracle имеет START_WITH и CONNECT_BY операторы: см. этот Иерархический документ Запросов.

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

Так или иначе хорошая вещь о карте сайта состоит в том, что Вы могли бы знать ее максимальную глубину. Я думаю, что проблема с моделью смежности состоит в том, что соответствующий SQL работает на одном уровне за один раз, поэтому если у Вас есть 'n' уровни затем, Вам нужен цикл 'n' SQL-операторов..., но я думаю (я не уверен), что, если Вы знаете максимум 'n' заранее затем, можно кодировать соответствующий fixed-number-of-multiple-levels SQL.

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

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

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