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

Question

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

Работает на MySQL (innoDB) со стеком LAMP.

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

Спасибо.

Answer 1

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

SQL how to store and navigate hierarchies

Which is the best database schema for my navigation

Answer 2

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

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

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

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

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

Answer 3

В статье Managing Hierarchical Data in MySQL подробно описано об этом.

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

Answer 4

Для полноты: Oracle имеет операторы START_WITH и CONNECT_BY: см. Этот Hierarchical Queries документ.

Answer 5

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

• смежности список ("parent_id" один почти каждый использует)
• Вложенных наборы
• Путь Перечисление
• Закрытие таблица (ака отношение смежности)

Смотрите мой ответ до "What is the most efficient/elegant way to parse a flat table into a tree?"

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

• "Trees and Hierarchies in SQL for Smarties" от Joe Celko.
• "SQL Design Patterns" Вадима Тропашко.

Answer 6

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

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

Джим,