Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / MySQL Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4   вперед  Ctrl      все
 FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
mahoune
Member

Откуда: Moscow
Сообщений: 5664
Древовидные структуры средствами MySQL

Задача:
Создать древовидную структуру данных. Обчно подобная структура необходима при хранении разных каталогов, прайс-листов, рубрикаторов и т.д.

Важно:
В обсуждении данного вопроса вы не найдете стандарного решения. Мы обсудим общие механизмы и подходы. Постараемся описать минусы и плюсы разных структур. И, надеюсь, скажем пару слов о том, что делать НЕ надо!

Все примеры будем рассматривать на каталоге товаров.

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

Поле Описание
ID Уникальный номер
ParentID Номер родительского раздела
CatName Название раздела


CREATE TABLE `Catalog` (
  `ID` INTEGER UNSIGNED NOT NULL AUTO_INCREMENT,
  `ParentID` INTEGER UNSIGNED NOT NULL,
  `CatName` VARCHAR(255) NOT NULL,
  PRIMARY KEY(`ID`)
);

В этой таблице поле ParentID указывает на родительский раздел, соответственно как-то надо обозначить тот раздел с которого начнется все дерево. Зачастую для этого используют значение 0 (ноль) в поле ParentID.

Теперь создаем таблицу товаров с ссылкой на каталог:

Поле Описание
ID Уникальный номер
CatID Номер раздела
GoodName Название товара


CREATE TABLE `Goods` (
  `ID` INTEGER UNSIGNED NOT NULL AUTO_INCREMENT,
  `CatID` INTEGER UNSIGNED NOT NULL,
  `GoodName` VARCHAR(255) NOT NULL,
  PRIMARY KEY(`ID`),
  CONSTRAINT `FK_Goods2Catalog` FOREIGN KEY `FK_Goods2Catalog` (`CatID`)
    REFERENCES `catalog` (`ID`)
    ON DELETE RESTRICT
    ON UPDATE RESTRICT
);

Заметьте, мы сразу, при создании таблицы товаров, задаем связь между полем CatID таблицы товаров (Goods) и полем ID таблицы разделов (Catalog).

Теперь для выбора товаров из одного определенного раздела достаточно выполнить скрипт:
SELECT g.*
FROM Goods g
WHERE CatID = 1;

Теперь поставим такую задачу, выбрать все продукты из данного раздела и всех его подразделов.

План
Рассказать про индексы.
Про связи.
Стандарные действия.
Поиск товаров.
Добавление разделов.
Удаление разделов и товаров.
Пермещение разделов и товаров.

Примеры преимуществ различных реализаций деревьев.

Неоформленный текст.
Теперь мы понимаем, что в больших и сложных проектах перво-наперво надо постараться определить основной характер взаимодействий с таблицей каталога и другими связанными с ней таблицами. Это существенно повлияет на выбор схемы организация дерева.

Модератор: Статья редактируется, пожелания и предложения в этот топик...
Присоединяйтесь! Спасибо!


.mahoune.
2 авг 09, 19:38    [7488767]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Alex_Ustinov
Member

Откуда: Nickel
Сообщений: 2911
неплохой простенький вариант "достать всех предков"
3 авг 09, 08:55    [7489308]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
mahoune
Member

Откуда: Moscow
Сообщений: 5664
Господа, помогите, я что-то не могу остановиться, все читаю и читаю статьи про деревья.
Думаю это абсолютно ни к чему.

Подскажите, что имеет смысл описать именно в FAQ, я же, в конце концов, не докторскую пишу.

.mahoune.
6 авг 09, 00:24    [7503341]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Alex_Ustinov
Member

Откуда: Nickel
Сообщений: 2911
можно просто сказать, что в MySQL одним запросом все дерево не достать.
Немного вариантов-ссылок на топики и имхо хорош.
6 авг 09, 15:26    [7506529]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
an0nym
Member

Откуда:
Сообщений: 7078
Alex_Ustinov
можно просто сказать, что в MySQL одним запросом все дерево не достать.
Немного вариантов-ссылок на топики и имхо хорош.

Я позволю себе с вами не согласится.

mahoune, ИМХО, стоит описать два самых распространенных способа работы с деревьями вообще - id+parent_id и вложенные множества. Указать, что способ id+parent_id в теории не ограничен уровнем вложенности (можно сделать очень много self joinов), но производительность будет не ахти. Способ вложенных множеств напротив очень удобен для выборки, но при изменении дерева необходимо обновлять много записей. Описать типовые операции для обоих деревьев (получение предков, сыновей, всего дерева).
6 авг 09, 17:59    [7507623]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
mahoune
Member

Откуда: Moscow
Сообщений: 5664
Я примерно в таком ключе и представлял себе.

Себе на заметку http://www.codenet.ru/db/other/trees/

.mahoune.
6 авг 09, 18:07    [7507665]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Alex_Ustinov
Member

Откуда: Nickel
Сообщений: 2911
an0nym,
согласен, но учитывая, что
mahoune в другом FAQ-топике все-таки заметил, что FAQ - не диссертация, учить как делать деревья думаю лишнее. Поэтому и написал, что можно дать ссылки на различные варианты.
6 авг 09, 18:12    [7507686]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 33571

an0nym пишет:

> сделать очень много self joinов), но производительность будет не ахти.
> Способ вложенных множеств напротив очень удобен для выборки, но при
> изменении дерева необходимо обновлять много записей. Описать типовые
> операции для обоих деревьев (получение предков, сыновей, всего дерева).

Давайте будем рассматривать возможность работы с деревьями на базе
in-depth-first search. Можно его сделать на SQL на структуре данных
на основе вложенных множеств ? Я сомневаюсь.

Posted via ActualForum NNTP Server 1.4

6 авг 09, 19:03    [7507855]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
an0nym
Member

Откуда:
Сообщений: 7078
MasterZiv

an0nym пишет:

> сделать очень много self joinов), но производительность будет не ахти.
> Способ вложенных множеств напротив очень удобен для выборки, но при
> изменении дерева необходимо обновлять много записей. Описать типовые
> операции для обоих деревьев (получение предков, сыновей, всего дерева).

Давайте будем рассматривать возможность работы с деревьями на базе
in-depth-first search. Можно его сделать на SQL на структуре данных
на основе вложенных множеств ? Я сомневаюсь.

Каюсь, по диагонали прочитал в Википедии про Depth-first_search, так что могу ошибаться в нижеописанном. SELECT id FROM nested_sets ORDER BY left ASC выдаст нам всё дерево, пройдя его так, как показано на данном рисунке. Вы имели в виду что-то другое?

Картинка с другого сайта.
6 авг 09, 21:55    [7508229]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Alex_Ustinov
Member

Откуда: Nickel
Сообщений: 2911
an0nym,
по ссылке mahoune -

в том случае
быстро выбирает все, но
проблемы с изменением родителя, т.е. очень затратно, как я понял. Сам такое не пробовал, каюсь.
Можно поднять какую-нибудь тему по деревьям, чтобы здесь не обсуждать.
И прав МАРАЗОТ - для каждого случая свое. Как надпись в Бухенвальде...
7 авг 09, 01:33    [7508770]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
RXL
Member

Откуда:
Сообщений: 1600
an0nym
Alex_Ustinov
можно просто сказать, что в MySQL одним запросом все дерево не достать.
Немного вариантов-ссылок на топики и имхо хорош.

Я позволю себе с вами не согласится.

mahoune, ИМХО, стоит описать два самых распространенных способа работы с деревьями вообще - id+parent_id и вложенные множества. Указать, что способ id+parent_id в теории не ограничен уровнем вложенности (можно сделать очень много self joinов), но производительность будет не ахти. Способ вложенных множеств напротив очень удобен для выборки, но при изменении дерева необходимо обновлять много записей. Описать типовые операции для обоих деревьев (получение предков, сыновей, всего дерева).


Производительность будет такая же, как и в других базах, вне зависимости, поддерживают ли они рекурсивные запросы. Сложность выборки по parent_id всегда N: N-1 производительных запросов и 1 пустой. Сложность поиска предков аналогичная. N - вложенность от исходного узла.

Выборка потомков одним запросом возможна только для строкового ключа. Выборка предков для него будет иметь сложность либо 1, либо N - зависит от обработки в клиенте.

В своей статье я рассказывал, как можно оба метода реализовать:
http://club.shelek.ru/viewart.php?id=307

В обсуждении на этом форуме предлагались и другие методы для текстового ключа, лишенные недостатков описанного у меня случая (который я тоже прочел в сети). Это альтернативный метод: "id1.id2.id3.". Кстати, поддерживаю его. Как вариант, можно на уровне клиента сжимать idЮ, переводя его из десятичного счисления в более высокие - вплоть до 256-иричного, но разделитель остается.

Метод индексации дерева left-right имеет недостаток в том, что изменение дерева всегда приводит к сложным изменениям всех узлов. Считаю, что это частный метод для статичных и редко изменяемых баз.
7 авг 09, 01:59    [7508783]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
RXL
Member

Откуда:
Сообщений: 1600
Метод текстового ключа на основе id.

CREATE TABLE tree (
  id INT UNSIGNED PRIMARY KEY,
  relation BINARY(255) NOT NULL UNIQUE
);

INSERT INTO tree VALUES
  (1, '1.'),
  (2, '1.2.'),
  (3, '1.2.3.'),
  (4, '1.4.'),
  (5, '1.2.5')
;

SELECT *
FROM tree
WHERE relation LIKE '1.2.%';

2  1.2
3  1.2.3.
5  1.2.5.
7 авг 09, 02:08    [7508787]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 33571

an0nym пишет:

> Каюсь, по диагонали прочитал в Википедии про Depth-first_search, так что
> могу ошибаться в нижеописанном. SELECT id FROM nested_sets ORDER BY left
> ASC выдаст нам всё дерево, пройдя его так, как показано на данном
> рисунке. Вы имели в виду что-то другое?

Нет, то же самое. Видимо, и впрямь возможно.

Posted via ActualForum NNTP Server 1.4

7 авг 09, 16:13    [7511929]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
mahoune
Member

Откуда: Moscow
Сообщений: 5664
RXL, на счет текстового ключа мне понравился немного другой метод который использовался в базе которая попала мне в руки.

Таблица выглядила так:

IDParentIDNameOrd
10'Родитель 1''00001'
20'Родитель 2''00002'
31'Потомок 1 Родитель 1''0000100001'
41'Потомок 2 Родитель 1''0000100002'
52'Потомок 1 Родитель 2''0000200001'
62'Потомок 2 Родитель 2''0000200002'


Так вот поле Ord выполняет несколько функций. Во-первых по нему легко задавать сортировку внутри родителя, что бывает необходимо на веб сайте, сортировка не по названию, а строго определенным порядком, позволяет найти всех потомков WHERE Ord LIKE '00001%' индексы по идее будут использоваться.

Найти всех родителей сложно за один запрос, а вот родителя определенного уровня сложности без проблем.

Я бы еще к этому добавитл таблицу с настройками где хранил сколько знаков на каждый уровень вложенности отводить, в данном случае 5 знаков. И использовал не фиксированное значение а вычисляемое.

В общем и целом выглядит достаточно просто.
7 авг 09, 17:44    [7512551]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
RXL
Member

Откуда:
Сообщений: 1600
У этого метода есть недостатоки:
1. Чтобы сгенерить новый идентификатор, нужно прочитать и просканировать все узлы ветки одного уровня, а если их нужно пересортировать, то обрабатывать придется всю ветку.
2. Число потомков лимитировано индексом.
3. Длинный индекс.

Согласен, что п.2 не очень важен, если заранее предположить объем ветвления, но тем не менее это лишает метод универсальности.
Насчет п.3 - можно и потерпеть.
А вот п.1. еще и ненадежен в многопоточном приложении.

В общем, я думаю, что метод не универсальный, но в специфичных условиях будет очень удобен.


В MySQL LIKE 'строка%' использует индексы при длине строки 2 символа и более (тестил в 5.0).
7 авг 09, 19:51    [7513038]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
maXmo
Member

Откуда: Моск.
Сообщений: 8555
небольшой сборник ссылок про деревья
http://www.sql.ru/forum/actualthread.aspx?tid=27688
26 авг 09, 15:14    [7582440]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
mahoune
Member

Откуда: Moscow
Сообщений: 5664
Nested Sets. Часть 1: Теория. Получение данных
Nested Sets. Часть 2: Теория. Работа с данными

Materialized Path. Часть 1: Теория. Получение данных
Materialized Path. Часть 2: Теория. Работа с данными

Автор Алексей Буянов

Ссылки пока не работают, но не убираю, вдруг сервер оживет!
26 апр 10, 17:27    [8691084]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
mahoune
Member

Откуда: Moscow
Сообщений: 5664
Ссылки:
Моделирование иерархических объектов
http://www.rsdn.ru/article/alg/dbtree.xml

Иерархические структуры данных в реляционных БД
http://www.rsdn.ru/article/db/Hierarchy.xml

Древовидные (иерархические) структуры данных в реляционных базах данных
http://ibase.ru/devinfo/treedb.htm

Древовидные (иерархические) структуры данных в реляционных базах данных,
часть 2
http://ibase.ru/devinfo/treedb2.htm

Работа с MySQL. Деревья
http://phpclub.ru/detail/article/2002-06-03

Хранение древовидных структур в Базах данных
http://phpclub.ru/detail/article/db_tree

Деревья в SQL
http://gsbelarus.com/gs/modules.php?name=News&file=article&sid=314

Дерево каталогов NESTED SETS (вложенные множества) и управление ими
http://www.getinfo.ru/article610.html

Деревья в SQL
http://www.codenet.ru/db/other/trees/

MySQL. Иерархические запросы
http://club.shelek.ru/viewart.php?id=307
8 июн 10, 02:36    [8905549]     Ответить | Цитировать Сообщить модератору
Между сообщениями интервал более 1 года.
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
NIIIK
Member

Откуда: Россия, Ростовская область, г. Таганрог
Сообщений: 1289
>Зачастую для этого используют значение 0 (ноль) в поле ParentID.

как потом констрейнт делаете (foreign key), создаёте запись с идентификатором ноль?
А если иденификаторы GUID?

По-моему "зачастую" надо создавать с NULL
11 сен 11, 13:30    [11260240]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
NIIIK
Member

Откуда: Россия, Ростовская область, г. Таганрог
Сообщений: 1289
В Оракле connect by prior довольно быстро работает, в MsSQL рекурсивные CTE применяются, но теперь есть ещё иерархический тип данных, написанный на С#, но который однозначно определяет является ли запись потомком этого родителя и обратно.

Идея его простая /0/5/1 - родительская запись, значит /0/5/1/1, /0/5/1/2, /0/5/1/N дочерние на один уровень вниз

/0/5/1
/0/5/2
/0/5/2.1
/0/5/3
/0/5/22

Записи одного уровня. 1, 2, 2.1, 3, 22 По сути порядок (внутри ветки)

Ну и соотвественно есть методы для определения "родителя", значения "между двумя значениями", проверки является ли запись дочерней.

Если в МуСКЛ готовые какие-то методы и т. п. с хорошим быстродействием (есть большая иерархическая таблица, быстродействие актуально)

С идеей а-ля
where ...
hierarchical_id like '/001/007/%'

И имеет ли это смысл на МуСКЛ по быстродействию ?
11 сен 11, 13:42    [11260262]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
NIIIK
Member

Откуда: Россия, Ростовская область, г. Таганрог
Сообщений: 1289
Вопрос отпал

http://club.shelek.ru/viewart.php?id=307
11 сен 11, 13:49    [11260277]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
никтогнито
Guest
drop table if exists employees;
create table employees
(
emp_id smallint unsigned not null auto_increment primary key,
name varchar(255) not null,
boss_id smallint unsigned null,
key (boss_id)
)
engine = innodb;

insert into employees (name, boss_id) values
('f00',null),
('ali later',1),
('megan fox',1),
('jessica alba',3),
('eva longoria',3),
('keira knightley',5),
('liv tyler',6),
('sophie marceau',6);


drop procedure if exists employees_hier;

delimiter #

create procedure employees_hier
(
in p_emp_id smallint unsigned
)
begin

declare v_done tinyint unsigned default(0);
declare v_dpth smallint unsigned default(0);

create temporary table hier(
boss_id smallint unsigned,
emp_id smallint unsigned,
depth smallint unsigned
)engine = memory;

insert into hier select boss_id, emp_id, v_dpth from employees where emp_id = p_emp_id;

/* http://dev.mysql.com/doc/refman/5.0/en/temporary-table-problems.html */

create temporary table emps engine=memory select * from hier;

while not v_done do

if exists( select 1 from employees e inner join hier on e.boss_id = hier.emp_id and hier.depth = v_dpth) then

insert into hier select e.boss_id, e.emp_id, v_dpth + 1
from employees e inner join emps on e.boss_id = emps.emp_id and emps.depth = v_dpth;

set v_dpth = v_dpth + 1;

truncate table emps;
insert into emps select * from hier where depth = v_dpth;

else
set v_done = 1;
end if;

end while;

select
e.emp_id,
e.name as emp_name,
p.emp_id as boss_emp_id,
p.name as boss_name,
hier.depth
from
hier
inner join employees e on hier.emp_id = e.emp_id
left outer join employees p on hier.boss_id = p.emp_id;

drop temporary table if exists hier;
drop temporary table if exists emps;

end #

delimiter ;

-- call this sproc from your php

call employees_hier(1);
3 фев 12, 18:00    [12029269]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
miksoft
Member

Откуда:
Сообщений: 36389
никтогнито,

и к чему эта серо-монотонная портянка кода в FAQ-овом топике?
3 фев 12, 18:03    [12029291]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Arhat109
Member

Откуда: из СССР
Сообщений: 3282
miksoft,

Н-да. посмотрел FAQ по деревьям, и прослезился... ни одной оценки тех или иных способов, ни конкретных решений, тем более специализированных под Мускуль... грустна.

Попробую для начал сделать так:
Тестовая машина - обычный комп с 2.5Ггц, древним Athlon-32, и 2 гектарами оперативки. LAMP-server.
Тестовые деревья: 500 деревьев с 3 ветками в каждом узле, глубина вложения узлов = 5 (всего 182000 записей) 100%заполнение узлов. В каждом дереве 363 потомка. Время парсинга мускулем запросов и прочие накладные расходы - в районе 50мсек. Включено в результаты тестирований (не вычиталось!)

1. Способы представления деревьев в реляционных БД и конкретно, применяемых на практике:

а) поле ссылки на родительский элемент в той же таблице (parent_id):
Достоинства:
- Наиболее компактный способ - расходы только дополнительное поле номера записи. Можно улучшить (например для сортировки), добавляя поле уровня текущего узла в дереве.

- , легко получаются выборки всех родителей от заданного узла: достаточно части WHERE parent_id = const. При нормально построенных индексах время выборки (описание условий выше) в районе 0.1сек.

- , легко ищутся прямые потомки и внуки узла: достаточно объединить табличку саму с собой. Время выборки в районе 0.1-0.12сек.

- , Операция вставки - тривиальна. Просто добавляем новый узел к родителю, прописывая идент родителя в узле

-, Проблемы вызывает поиск ВСЕХ потомков от заданного узла. Типовые, предлагаемые решения через последовательные JOIN и UNION -- или громоздки в построении, или предполагают знание или ограничение уровней вложенности. В тестовом примере выше (ограничена глубина дерева = 5), время выполнения составного union и последовательных Join - в районе 0.15 - 0.2сек.

-, При наличии поля level и неограниченной глубине и "ветвистости" дерева, можно, поизвращавшись с переменными Мускуля, посторить один запрос (на одном само-join), который будет вытаскивать всех потомков. Время работы на тестовом примере 0.7сек. Показывает ещё более лучшее время при росте глубины деревьев при небольшой "ветвистости" узлов. Особенно в вырожденных случаях, когда большая часть узлов на разных уровнях не имеет потомков (время выборок в районе 0.25сек и меньше). Хуже при широких и не глубоких деревьях.
На тестовом примере из 21844 узлов для 4-х деревьев (ветвистость=4, глубина=6, всего узлов в одном дереве 5460), показал примерно такую же скорость - 0.5сек.

б) Построение дерева на таблице связи "parent, child, level". Понятно что поиск по индексам дает наибольшую скорость выборок. Тестовый пример - 0.12сек. Для тестового примера таблица индесков разрослась до 820500 записей (без связей узлов "сам с собой" - ищем только потомков заданного без самого узла. Его и так знаем. :)

- ?!? Как ни странно, основным доводом "против" приводят именно размер таблицы связи... от базовой отличается всего в 4 раза, а если учесть, что в базовой таблице никаких полей хранить НЕ требуется, то потери итого меньше. А если учесть, что на практике деревья редко бывают 100% заполненными - потери становятся несущественными.

В реальности на каждый добавляемый узел расходуется depth-1 запись в таблице. Операции вставки требуют дополнительного добалвения такого количества записей "вручную" (за этим надо следить!), операция удаления в ситуации внешних ключей - проблем не вызывает. Операция переноса требует изменения всех связанных записей с этим узлом...

Итого: для широких (с большим числом ветвей) и не глубоких деревьев - решение с таблицей связи оказалось наиболее оптимальным для меня в большинстве применений.

в) Nested Sets... я ваще как-то слабо понял где оно полезно. С точки зрения выборок оно нисколько не лучше таблиц связи. На каждый узел хранится номер, левый, правый интервал и уровень - 4 числа. Таблицы связи с глубиной 3 - ещё и компактнее.
Добавить 3 узла в тестовый пример в середину дерева - я просто не дождался, когда оно кончит крутить винт... больше 30сек - получилось всяко. Может я его неправильно готовил?!?

г) Список всех потомков узла в дополнительном поле родителя. При выборках в 2 приема - выбираем узел и используем строку этого поля как часть запроса IN(...). Время выборки по тестовому примеру тоже в районе 0.15сек.
Выборка в 2 этапа бывает чаще чем кажется при ООП, особенно при организации в иерархию разнородных объектов (из разных таблиц БД с разной структурой): подгрузили activeRecord об узле в одном методе (например ещё на этапе инициализации ответа на запрос) а в нужном месте тупо ищем потомков.

Недостаток - много места, для хранения небольшого количества узлов. При 6 значных номерах узлов - в 256 умещается 32 узла... маловато.
Вторая проблема - перемещения узлов... требуется корректировка списка у всех родительских узлов данного потомка...

д) Составной индекс узла (правый или левый - собственно все равно). Выборка всех потомков - через использование оператора LIKE. К сожалению нормально запинать не удалось - оставалось уже мало времени, а собрать в запросе шаблон из части индекса заданного узла, отрезая на ходу "лишнее" - сразу не получилось...

Недостаток: имхо Like - это плохо, перенос узла требует тщательной перенумерации оставшихся (перенос средней ветки) или учета "дыр" в нумерации. Опять же, можно применять для небольших (не глубоких, и не широких) деревьев. И не сравнивал, но для деревьев такого типа, насколько догадываюсь - проиграет таблице связей по размерам.

Ну вот. На скорую руку, пока всё. Код не приводил сознательно - он может быть разным. Кому что нужнее от деревьев.

Ещё раз ИМХО: деревья, созданные на таблицах связи - лучшее решение для большинства применений. Плохо только с большим количеством сильно глубоких (depth > 10..100) и неветвистых(childs < 10) деревьев. В таких случаях вариант "а" - самое то.
12 июл 12, 17:07    [12858390]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
miksoft
Member

Откуда:
Сообщений: 36389
Arhat109
ни одной оценки тех или иных способов, ни конкретных решений, тем более специализированных под Мускуль... грустна.
Согласен, самому "грустна".
Но чтобы ставить метрологически корректные эксперименты нужно немало времени, которого пока не нашлось.

И, вроде бы, MySQL вообще не имеет специализированных решений и способов для хранения и обработки иерархических структур данных.
12 июл 12, 17:16    [12858464]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4   вперед  Ctrl      все
Все форумы / MySQL Ответить