Иерархические данные нужны всюду. Меню содержания сайта, группирование людей, каталоги продуктов, интранет документы, файловая система и тп.
«Породы» деревьев
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%';
Самый простой, но не масштабируемый вариант
- Получаем всё дерево
- Получаем найденные элементы
- Находим для всех найденных элементов путь вверх и сохраняем все эти пути в одно множество A.
- Начинаем показ всего дерева и фильруем показ элементов, показывая только те, которые есть в множестве A
Немного более сложный вариант
- Получаем найденные элементы
- Для каждого элемента находим путь до корня вверх, сохраняем последовательно все элементы пути в множество B.
- Начинаем с корня меню, спускаемся сверху вниз, ища элементы среди множества 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;
}
Источники: