Часто нам приходиться сталкиваться с проблемой хранения деревьев в базе, например, дерево категорий товаров в типичном приложении Интернет-магазина. Наверное самый простой способ – это хранить данные о родителе. Самый удобный, на мой взгляд, с точки зрения добавления, редактирования и удаления. Но не самый удобный для построения.
Один из вариантов деревьев, которые мне понравились в использовании – это деревья с левым и правым индексом – советую их использовать при больших объёмах данных, т.к. такие операции, как выборка поддерева, построения дерева линейны и не требуют дополнительного кода. Про эти деревья можно почитать здесь.
Я решил не мучаться, и использовать доработанный первый вариант – сохранять ещё и уровень вложенности.
Таким образом, в базе храняться поля id, parent_id, level, name (parent_id=0 – это корень дерева)
Что надо для выборки и построения дерева?
1. Выбрать записи из базы, предварительно отсортировать по level и parent_id
$rows = $sql->fetchRowsById('SELECT *
FROM categories
ORDER BY level,parent_id,name');
// в результате мы имеем ассоциативный массив с id категории в роли ключа 2. Дальше подготавливаем его для сортировки
$currlvl = 0;
$counter = 0;
foreach ($rows as $id => $category) {
if ($category['level'] > $currlvl) {
$counter = 0;
$currlvl++;
}
$pre = '';
$parent_id = $category['parent_id'];
if (isset($rows[$parent_id])) {
$pre = $rows[$parent_id]['_sort_v'];
}
$rows[$id]['_sort_v'] = $pre.sprintf("%03x", $counter);
// вносим служебное поле, своего рода порядковый номер $counter++;
//данный ход сделан для того, чтобы сортировать, используя строковые функции
//тут используется ограничение на 1024 вложенных категорий, в принципе можно расширить и до 65К,
}
uasort($rows, create_function('$a, $b','return strcmp($a[_sort_v],$b[_sort_v]);'));
//собственно сортировка, в результате которой мы получаем дерево вложенностиПодводные камни - целостность базы. Так же нужен дополнительный код для операций добавления, перемещения и удаления узлов. В целом метод себя успешно зарекомендовал и используется, и нравиться тем, что время линейно (не считая работы sql и uasort.
P.S. данный метод хранения удобен так же при работе с Tree компонентами, т.к. на каждой итерации добавления узла родитель уже присутствует в дереве.
А каким образом вы храните и строите деревья?
Loading ...
марта 14, 2007 в 12:17 pm
А мы с оными неработаем. Неприходилось
марта 14, 2007 в 4:08 pm
В современных движках баз данных давно придумали такое понятие, как иерархический запрос. Именно для таких вот случаев работы с деревьями. В дибиту, например, эта проблема решаеться очень элегантно. Там есть уникальная поддержка рекурсивных запросов.
марта 14, 2007 в 5:39 pm
рекурсивный запрос сосёт по сравнению с лево-правыми деревьями. но если учитывать факт кеширования - тогда да, не спорю
марта 14, 2007 в 6:30 pm
Большое спасибо Гледу за возвращение к программерским темам. А то я боялся что Райан скоро начнет о городской политике тут писать
На счет вопроса "как хранить деревья?" - некорректный вопрос. Надо спрашивать "как хранить деревья если критическая операция така-то". Потому что если важней всего скорость поиска, то лево-правые деревья не подходят однозначно
Теперь важный момент - вставка кода в посты. Сейчас это очень нехорошо выглядит
Сделайте что-нибудь, пожалуйста.
Для подсветки можно использовать:
http://softwaremaniacs.org/soft/highlight/
Ну и pre автоматически подставлять, а то отступы слетают страшно.
марта 14, 2007 в 7:56 pm
Да мля, может нах выкинуть этот вордпресс
хотя надо заэксплорить тему, или убрать этот визивиг нафик
марта 14, 2007 в 8:50 pm
визвиг это что?
какая альтернатива вордпресу?
highlight я попробую интергрировать
марта 14, 2007 в 9:10 pm
визивиг редактор текстов в вордпрессе
марта 15, 2007 в 12:38 pm
Для простых задач рекурсией
Для больших статических объемов (географические обьекты классика страна-штат-графство-город-район) вложенными множествами - рекурсия приводит к жестким тупнякам(сервер MySQL:))
Классов реализующих работу с NestedSets вообщето достаточно думаю для всех языков.
марта 15, 2007 в 9:27 pm
В случае, если у категории может быть только один родитель, мне хватает одной таблицы, ссылающейся сама на себя.
CREATE TABLE "types" (
"id" SERIAL,
"refParent" INTEGER,
"name" VARCHAR(255) NOT NULL,
CONSTRAINT "types_pkey" PRIMARY KEY("id"),
CONSTRAINT "fkeyParentId" FOREIGN KEY ("refParent")
REFERENCES "types"("id")
ON DELETE CASCADE
ON UPDATE CASCADE
NOT DEFERRABLE
) WITHOUT OIDS;
Когда пользователь выбрал узел и хочет его раскрыть, следующий уровень выбирается по имени выбранного узла NODE_NAME (вместо имени можно выбрать любой потенциальный ключ):
select name
from "types"
where "types"."refParent" = (
select id from "types" where name='NODE_NAME'
);
Насчет хранить уровень идея хорошая, при вставке узла в середину дерева каскадом надо будет декрементировать значения уровня подлежащих узлов, а при удалении -- инкрементировать.
Групповые операции по такому дереву не проводил. Хотя в один запрос вместить такое тяжело.
Про множества почитал, но мне кажеться можно сделать как-то проще, слишком уж громоздкое решение.
марта 16, 2007 в 5:23 pm
А почему бы не отказаться от реляционной модели в пользу иерархического хранилища?
марта 16, 2007 в 8:50 pm
Это чего например? LDAP что ли?
марта 16, 2007 в 10:43 pm
Ну это редко главная задача.А при нормальном инструментарии рутина и сложности прячутся.
марта 22, 2007 в 12:42 am
2 Руслан Пилин
например файловая система.
мая 7, 2008 в 10:01 am
Спасибо было полезно, узнал много нового