Иерархические данные нужны всюду. Меню содержания сайта, группирование людей, каталоги продуктов, интранет документы, файловая система и тп.

«Породы» деревьев

Adjacency list — самый простой способ, с которого начинает практически каждый. У каждого элемента есть параметр parentID. Очень простой способ, но получение всего пути для каждого элемента вызывает лишние запросы пропорционально глубине элемента.

Materialized path — adjacency list дополняется перечислением всех предков для каждого элемента. Пропорциональный overhead в зависимости от глубины дерева, но дисковое пространство и индекс даже не столько критичны сколько ограничение на изменение ветки, ведь должны изменится все дочерние элементы.

Хранение пути реализуется либо как одно поле, либо как фиксированное количество колонок id1, id2 … idN с множеством JOIN’ов, но последний вариант не очень практичен, поскольку при фиксированной глубине дерева можно обойтись и JOINом adjacency listа самого на себя, просто N-ое количество раз.

Nested set — вместо id родителя используются два числа, означающие границы своих детей при полной линеаризации дерева. Очень быстрая и лёгкая выборка веток противопоставляется проблематичным добавлением новых веток, ведь для этого надо поменять границы у всего дерева.

Nested Intervals — как решение проблемы добавления нового элемента в nested sets, предлагается использовать дырки между интервалами. Тогда либо ограничивать добавление этими оставшимися дырами, либо перераспределять периодически эти пустоты. При больших объемах данных и больших дырках вероятно что целочисленного типа (int) может не хватить

Поиск с подсветкой

Поставим такую задачу — при поиске в меню надо показывать только ветки с ключевым словом и родительские ячейки. Детей глубже показывать не стоит.

Стандартный поиск по таблице дело простое — делаем запрос и получаем на выходе результат — список:

SELECT * FROM myarticles WHERE articleTitle LIKE '%myword%';

Самый простой, но не масштабируемый вариант

  1. Получаем всё дерево
  2. Получаем найденные элементы
  3. Находим для всех найденных элементов путь вверх и сохраняем все эти пути в одно множество A.
  4. Начинаем показ всего дерева и фильруем показ элементов, показывая только те, которые есть в множестве A

Немного более сложный вариант

  1. Получаем найденные элементы
  2. Для каждого элемента находим путь до корня вверх, сохраняем последовательно все элементы пути в множество B.
  3. Начинаем с корня меню, спускаемся сверху вниз, ища элементы среди множества B с соответсвующим parentID

Рекурсивная функция построения дерева использует метод buildSearchLevel, которая возвращает просто список дочерних элементов.
function searchTree($parentNode, $parentNodeLevel){
$arrTree=array();
$arrLevel=$this->buildSearchLevel($parentNode);
if (is_array($arrLevel))
foreach ($arrLevel as $node){
$node->level=$parentNodeLevel+1;
$arrTree[]=$node;
$arrTree=array_merge($arrTree, $this->searchTree($node->ID, $node->level));
}
return $arrTree;
}

Источники:


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *