|
MySQL.RU - Webboard
 Вернуться
 Многоуровневый каталог (Виктор) 13/07/2004 - 14:59:36
 Re: Многоуровневый каталог (Alec) 13/07/2004 - 15:27:58
Re: Многоуровневый каталог (Валентин) 13/07/2004 - 16:44:16
Re: Многоуровневый каталог (Андрей) 14/07/2004 - 11:52:08
Re: Несколько способов (Sam) 14/07/2004 - 14:38:26
Re: Несколько способов (Валентин) 14/07/2004 - 16:09:48
Re: Несколько способов (Виктор) 14/07/2004 - 16:47:28
> Original message text:
> From: Виктор - 13/07/2004 - 14:59:36
> Subject:Многоуровневый каталог
> -----------------
> Джентельмены!
>
> простая задача - нужно хранить в БД каталог, потенциально большого размера (более десятка тысяч записей, чем и обуслевлено требование хранения в бд) произвольного уровня вложенности с быстрым доступом к произвольным данным.
>
> Я взял за основу ссылку на родителя элемента и пытаюсь строить часть дерева.
>
> структура таблицы:
> ID
> parentID
> hasChilds
>
> nodeName
> value
>
> последние два определяют данные элемента каталога, а дерево получается за счет связки ID-parentID. hasChilds стопер, обновляется при добавлени и удалении елементов для parentID.
>
> Как я строю меню по этому дереву
> 1) нахожу текущий элемент, например, по значению (один запрос)
> 2) строю цепочку его родителей к корню (по parentID), чтобы активировать всю ветвь (отдельный запрос на каждый елемент :( )
> 3)затем нахожу всех соседей, т.е детей parentID (еще один запрос).
>
> есть ли более быстрая схема? Можно ли и стоит ли упаковывать шаг 2 в один запрос (и собственно как :) )?
>
From: Sam - 14/07/2004 - 14:38:26
Subject:Несколько способов
-----------------
1. Использовать в качестве идентификаторов не autonumbers, а специально сформированный номер.
Корень дерева - 0x00000000
Первый эл. в корне - 0x01000000
Второй эл. в корне - 0x02000000
Первый потомок первого эл. в корне - 0x01010000
Первый потомок второго эл. в корне - 0x02010000
Тогда номера родителей можно получить битовыми масками.
А выбрать всех потомков (рекурсивно) можно по диапазону номеров
id > 0x01000000 AND id < 0x02000000
Достоинство - легко добавлять, легко удалять, легко переносить целые ветки.
Недостаток - кол-во элементов в корне 127, в лубом другом узле - 255. Глубина вложенности 4 (если id 32 битовое поле)
Еще один недостаток - меняются ID элементов при перемещении.
2. То же что и первое, но кол-во бит для каждого элемента не фиксировнно.
Дерево из первого примера будет выглядеть так.
Корень 0
Первый в корне 1
Первый потомок первого 2
Второй в корне 3
Второй потомок второго 4
(то есть если развернуть дерево - то все узлы будут пронумерованны сверху вниз по порядку)
Достоинство легко выбирать ветки рекурсивно
id > [id родителя] AND id < [id следующего родителя родителя]
[id следующего родителя родителя] вычисляется как min(id) WHERE pid = current_pid
Легко удалять ветки. Нет ограничений на структуру дерева.
Недостатки - все. Вставлять сложно, id при манипуляциях меняются, переносить ветками - ужастно сложно, выбрать всех родителей тоже сложно.
3. Комбинированный. Табличка как у тебя. id (autonumber, PRIMARY KEY), pid (FOREIGN KEY)
Только не нужно избыточное поле has_child (значение этого поля легко вынуть из базы Exist(SELECT id WHERE pid = current_id)
Вставку, замену, перенос ветвями и все, что угодно делаем с этой табличкой, за исключением выбора ветки рекурсивно.
А выбор рекурсивно и удаление делаем из другой таблички
id
pid
num
pnum
где id и pid такие как у тебя, a num - такие как id в примере 2. pnum - то что и pid, но ссылается на num и не имеет NULL, вместо него используется 0 как признак того что эл. принадлежит корню.
Выбор ветки целиком делаем так
SELECT t.* FROM tree WHERE id IN (SELECT id FROM cache WHERE num > num_of_current AND num < num_of_next_parent)
Предварительно вычисляем num_of_parent
SELECT num FROM cache WHERE id = current_id
А также вычисляем num_of_next_parent
SELECT min(num) FROM cache WHERE pnum = current_pnum
Может оказаться что этот запрос вернет NULL тогда выбор ветки делается чуть проще
SELECT t.* FROM tree WHERE id IN (SELECT id FROM cache WHERE num > num_of_current)
Точно так же можно удалять ветки.
DELETE tree WHERE id IN (SELECT id FROM cache WHERE num > num_of_current)
[Это сообщение - спам!]
Последние сообщения из форума
Уважаемые посетители форума MySQL.RU!
Убедительная просьба, прежде чем задавать свой вопрос в этом форуме, обратите внимание на разделы:
- ответы на наиболее часто задаваемые вопросы - FAQ
- раздел документация
- раздел поиск по сообщениям форума и документации
Также, старайтесь наиболее подробно указывать свою ситуацию (версию операционной системы, версию MySQL,
версию программного обеспечения, по которому возникает вопрос, текст возникающих ошибок, и др.)
Помните, чем конкретнее Вы опишете ситуацию, тем больше шансов получить реальную помощь.
16074
|
|
