ReSQL.ru
     
powered by simpleCommunicator - 2.0.44     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / MySQL [игнор отключен] [закрыт для гостей] / FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
78 сообщений из 78, показаны все 4 страниц
  все  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36122190
Фотография mahoune
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mahoune
Участник
Древовидные структуры средствами MySQL

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

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

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

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

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

Код: plaintext
1.
2.
3.
4.
5.
6.
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 Название товара

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
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).

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

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

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

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

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

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

Код: plaintext
.mahoune .
...
Рейтинг: 0 / 0
02.08.2009, 19:38
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36122507
Фотография Alex_Ustinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alex_Ustinov
Участник
неплохой простенький вариант " достать всех предков "
...
Рейтинг: 0 / 0
03.08.2009, 08:55
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36128925
Фотография mahoune
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mahoune
Участник
Господа, помогите, я что-то не могу остановиться, все читаю и читаю статьи про деревья.
Думаю это абсолютно ни к чему.

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

Код: plaintext
.mahoune .
...
Рейтинг: 0 / 0
06.08.2009, 00:24
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36130329
Фотография Alex_Ustinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alex_Ustinov
Участник
можно просто сказать, что в MySQL одним запросом все дерево не достать.
Немного вариантов-ссылок на топики и имхо хорош.
...
Рейтинг: 0 / 0
06.08.2009, 15:26
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36130965
an0nym
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
an0nym
Участник
Alex_Ustinovможно просто сказать, что в MySQL одним запросом все дерево не достать.
Немного вариантов-ссылок на топики и имхо хорош.
Я позволю себе с вами не согласится.

mahoune, ИМХО, стоит описать два самых распространенных способа работы с деревьями вообще - id+parent_id и вложенные множества. Указать, что способ id+parent_id в теории не ограничен уровнем вложенности (можно сделать очень много self joinов), но производительность будет не ахти. Способ вложенных множеств напротив очень удобен для выборки, но при изменении дерева необходимо обновлять много записей. Описать типовые операции для обоих деревьев (получение предков, сыновей, всего дерева).
...
Рейтинг: 0 / 0
06.08.2009, 17:59
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36130986
Фотография mahoune
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mahoune
Участник
Я примерно в таком ключе и представлял себе.

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

Код: plaintext
.mahoune .
...
Рейтинг: 0 / 0
06.08.2009, 18:07
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36130997
Фотография Alex_Ustinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alex_Ustinov
Участник
an0nym,
согласен, но учитывая, что
mahoune в другом FAQ-топике все-таки заметил, что FAQ - не диссертация, учить как делать деревья думаю лишнее. Поэтому и написал, что можно дать ссылки на различные варианты.
...
Рейтинг: 0 / 0
06.08.2009, 18:12
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36131102
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
an0nym пишет:

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

Давайте будем рассматривать возможность работы с деревьями на базе
in-depth-first search. Можно его сделать на SQL на структуре данных
на основе вложенных множеств ? Я сомневаюсь.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
06.08.2009, 19:03
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36131292
an0nym
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
an0nym
Участник
MasterZiv
an0nym пишет:

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

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

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

...
Рейтинг: 0 / 0
06.08.2009, 21:55
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36131401
Фотография Alex_Ustinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alex_Ustinov
Участник
an0nym,
по ссылке mahoune -

в том случае
быстро выбирает все, но
проблемы с изменением родителя, т.е. очень затратно, как я понял. Сам такое не пробовал, каюсь.
Можно поднять какую-нибудь тему по деревьям, чтобы здесь не обсуждать.
И прав МАРАЗОТ - для каждого случая свое. Как надпись в Бухенвальде...
...
Рейтинг: 0 / 0
07.08.2009, 01:33
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36131405
RXL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RXL
Участник
an0nymAlex_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 имеет недостаток в том, что изменение дерева всегда приводит к сложным изменениям всех узлов. Считаю, что это частный метод для статичных и редко изменяемых баз.
...
Рейтинг: 0 / 0
07.08.2009, 01:59
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36131407
RXL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RXL
Участник
Метод текстового ключа на основе id.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
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 .
...
Рейтинг: 0 / 0
07.08.2009, 02:08
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36132720
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
an0nym пишет:

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

Нет, то же самое. Видимо, и впрямь возможно.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
07.08.2009, 16:13
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36132926
Фотография mahoune
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mahoune
Участник
RXL, на счет текстового ключа мне понравился немного другой метод который использовался в базе которая попала мне в руки.

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

IDParentIDNameOrd10'Родитель 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 знаков. И использовал не фиксированное значение а вычисляемое.

В общем и целом выглядит достаточно просто.
...
Рейтинг: 0 / 0
07.08.2009, 17:44
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36133140
RXL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RXL
Участник
У этого метода есть недостатоки:
1. Чтобы сгенерить новый идентификатор, нужно прочитать и просканировать все узлы ветки одного уровня, а если их нужно пересортировать, то обрабатывать придется всю ветку.
2. Число потомков лимитировано индексом.
3. Длинный индекс.

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

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


В MySQL LIKE 'строка%' использует индексы при длине строки 2 символа и более (тестил в 5.0).
...
Рейтинг: 0 / 0
07.08.2009, 19:51
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36164223
maXmo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
maXmo
Участник
небольшой сборник ссылок про деревья
http://www.sql.ru/forum/actualthread.aspx?tid=27688
...
Рейтинг: 0 / 0
26.08.2009, 15:14
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36599023
Фотография mahoune
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mahoune
Участник
Nested Sets. Часть 1: Теория. Получение данных
Nested Sets. Часть 2: Теория. Работа с данными

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

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

Ссылки пока не работают, но не убираю, вдруг сервер оживет!
...
Рейтинг: 0 / 0
26.04.2010, 17:27
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #36674474
Фотография mahoune
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mahoune
Участник
Ссылки:
Моделирование иерархических объектов
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
...
Рейтинг: 0 / 0
08.06.2010, 02:36
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #37434713
NIIIK
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NIIIK
Участник
>Зачастую для этого используют значение 0 (ноль) в поле ParentID.

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

По-моему "зачастую" надо создавать с NULL
...
Рейтинг: 0 / 0
11.09.2011, 13:30
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #37434725
NIIIK
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NIIIK
Участник
В Оракле 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/%'

И имеет ли это смысл на МуСКЛ по быстродействию ?
...
Рейтинг: 0 / 0
11.09.2011, 13:42
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #37434731
NIIIK
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NIIIK
Участник
Вопрос отпал

http://club.shelek.ru/viewart.php?id=307
...
Рейтинг: 0 / 0
11.09.2011, 13:49
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #37646312
никтогнито
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
никтогнито
Гость
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);
...
Рейтинг: 0 / 0
03.02.2012, 18:00
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #37646321
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
никтогнито,

и к чему эта серо-монотонная портянка кода в FAQ-овом топике?
...
Рейтинг: 0 / 0
03.02.2012, 18:03
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #37876996
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
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) деревьев. В таких случаях вариант "а" - самое то.
...
Рейтинг: 0 / 0
12.07.2012, 17:07
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #37877024
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Arhat109ни одной оценки тех или иных способов, ни конкретных решений, тем более специализированных под Мускуль... грустна.Согласен, самому "грустна".
Но чтобы ставить метрологически корректные эксперименты нужно немало времени, которого пока не нашлось.

И, вроде бы, MySQL вообще не имеет специализированных решений и способов для хранения и обработки иерархических структур данных.
...
Рейтинг: 0 / 0
12.07.2012, 17:16
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #37877186
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
miksoft,

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

Если не проходит вариант с таблицей (много сильно глубоких деревьев), то или вариант "а" с запросом через переменные или разбивка на несколько таблиц (где-то в ваших ссылках есть вполне нормальное описание про фиксированное вложение каталогов)...
...
Рейтинг: 0 / 0
12.07.2012, 18:32
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #37877855
RXL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RXL
Участник
miksoftвроде бы, MySQL вообще не имеет специализированных решений и способов для хранения и обработки иерархических структур данных.

В ответвлении MariaDB есть "движок" для графов - OQGRAPH, но с готовые бинарники его включают не во все, т.к. он основан на boost довольно высокой версии. Кроме того, по отзывам пользователей, на больших масштабах (порядка млн узлов) скорость работы неудовлетворительная.
...
Рейтинг: 0 / 0
13.07.2012, 11:53
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38087077
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Топик, в котором родилось решение для написания иерархических запросов.
/topic/984179
...
Рейтинг: 0 / 0
20.12.2012, 16:23
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38090159
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
miksoft, пасибки. Поисследовал этот вопрос ишо раз.

Вот "тот самый" запрос о котором писал впервые тут 12858390 "поизвращавшись с переменными" (дали добро):

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
SELECT
  @idx := substring_index(@array, ',', 3) AS child
  , @array := CONCAT( REPLACE(@array, @idx, ''), (
      SELECT IFNULL(GROUP_CONCAT(CONCAT(',',`id`,',') SEPARATOR ''), '')
      FROM `tree`
      WHERE `parent_id` = REPLACE(@idx, ',', '')
  )) AS array
FROM (SELECT @array:=',9,') AS dummy
, `tree`
WHERE LENGTH(@array) > 0
;



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

В ряде относительно простых случаев (ограничения на структуру таблицы), подходит вот такое "скоростное" решение:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
SELECT
  ch.`id` AS child, ch.`parent_id` AS parent, ch.`level` AS level
  , @array := CONCAT(@array, CONCAT(',',ch.`id`,',')) AS array
FROM (SELECT @array:=',9,') AS dummy
, `tree1` AS ch  FORCE INDEX (level)
WHERE
  LOCATE(CONCAT(',',ch.`parent_id`,','), @array) > 0
;
--# индекс: `level` (`level`,`parent_id`,`id`) лучше делать единственным и первичным ключом таблицы
--# тогда можно не прибивать гвоздями...
--# В этом случае надо забыть про автоинтремент, требующий собственного отдельного индекса...



оно также НЕ избегает фулл-скана, но уже только индекса и НЕ содержит некешируемых подселектов... собственно никаких не содержит. Это вариант "чистого" курсора.
... 1. "поизвращавшись с переменными" ещё немного, можно во втором варианте также сделать удаление ненужных узлов из накапливаемого массива @array.
... 2. "поизвращавшись с переменными" можно слегка улучшить первый вариант, устранив подселект для конечных листьев, где он дает гарантированно пустой результат. Вообще-то их - много, и как правило больше чем рабочих веток.

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

Не надо ТАК делать.
Для себя - как вопрос "самообразования" - задача интересна, но и только. Везде где можно, заменил на нормальную и полноценную таблицу связи. Пусть уж жрет память, чем тормозит не по-детски.
...
Рейтинг: 0 / 0
24.12.2012, 07:49
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38157937
DBConstructor
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DBConstructor
Участник
Никаких "фул сканов", выбираются только строки потомков. Результат в строковой переменной @branch, в виде идентификаторов всех членов ветви, разделенных запятой.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
SET @branch='3';
SELECT @branch as branch
  FROM `Catalog`
  WHERE EXISTS (SELECT 
         @branch:=Concat_ws(',', @branch, group_concat(`ID`)) branch
       FROM `Catalog`
       WHERE Find_in_set(`ParentID`, @branch)
         AND NOT Find_in_set(`ID`, @branch)
       GROUP BY `ParentID`
       ORDER BY `branch` DESC LIMIT 1)
  ORDER BY `branch` DESC LIMIT 1;
...
Рейтинг: 0 / 0
19.02.2013, 19:13
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38158085
tanglir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tanglir
Участник
DBConstructor Никаких "фул сканов" , выбираются только строки потомков.А разве Find_in_set умеет использовать индексы?
...
Рейтинг: 0 / 0
19.02.2013, 21:21
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38158127
DBConstructor
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DBConstructor
Участник
tanglirDBConstructor Никаких "фул сканов" , выбираются только строки потомков.А разве Find_in_set умеет использовать индексы?

Извини, не понял вопроса. Причем тут индексы? Это один из вариантов, использующий строку в качестве хранения идентификаторов членов ветви. Но этот вариант, благодаря тому, что подзапрос с группировкой и объединением идентификаторов потомков перестает возвращать строки в случае, если идентификаторы всех членов ветви уже находятся в переменной @branch, не использует "фул скан" и выполняет ровно то количество итераций, которое необходимо для получения результата.
...
Рейтинг: 0 / 0
19.02.2013, 22:07
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38158340
tanglir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tanglir
Участник
DBConstructor, я имел в виду, что, хотя этот запрос может и не добраться до конца таблицы и тем самым "снаружи" фулскана, скорее всего, не получится, но подзапрос в EXISTS будет фулсканить таблицу `Catalog`, т.к. Find_in_set-у никакие индексы тут не помогут.
...
Рейтинг: 0 / 0
20.02.2013, 06:06
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38158393
DBConstructor
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DBConstructor
Участник
tanglir, не вижу большой разницы между выборкой всех страниц индексов связывания двух таблиц с последующим совмещением этих индексов и последовательной проверкой значения одного поля одной таблицы с константной строкой.
Мне, почему-то даже кажется, что второе будет быстрее первого.
...
Рейтинг: 0 / 0
20.02.2013, 08:22
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38159840
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
DBConstructor,

протестил:

1. Таблица 10 деревьев по 1 листу в уровне, всего 300 уровней (3000 записей всего!)
2. Решение Бочкова дает выборку от 0,5 до 1 сек.
3. Решение с составным индексом (моё тут последнее) дает 50-80мсек.
4. Ваше решение проработало больше (уже 705сек и ещё пашет)... сколько точно - не знаю.

как-то так. :)
...
Рейтинг: 0 / 0
20.02.2013, 22:37
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38159861
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
Arhat109,

а конкретно, всё банально: подселект выполняется также как и в варианте Бочкова, только там есть ещё группировка и сортировка... и применить индексы - практически некуда.
...
Рейтинг: 0 / 0
20.02.2013, 23:03
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38161035
DBConstructor
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DBConstructor
Участник
Arhat109Arhat109,

а конкретно, всё банально: подселект выполняется также как и в варианте Бочкова, только там есть ещё группировка и сортировка... и применить индексы - практически некуда.

Нет, не банально! Простой пример:

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
DROP TABLE IF EXISTS `catalog`;
CREATE TABLE IF NOT EXISTS `catalog` (
    `id`    INT UNSIGNED NOT NULL AUTO_INCREMENT,
    `parent_id` INT UNSIGNED DEFAULT NULL,
    `status`    ENUM('USED', 'DELETED') DEFAULT 'USED' NOT NULL,
  CONSTRAINT `categories__pk` PRIMARY KEY (`id`)
);

DROP PROCEDURE IF EXISTS `fill__catalog`;
DELIMITER //
CREATE PROCEDURE `fill__catalog`(
    IN rowCount INT UNSIGNED)
  LANGUAGE SQL
  NOT DETERMINISTIC
  CONTAINS SQL
  SQL SECURITY INVOKER
BEGIN
  DECLARE i INT UNSIGNED DEFAULT 0;
  DECLARE ParentId INT UNSIGNED DEFAULT 0;
  REPEAT
    SET ParentId = (SELECT Round(Rand()*Max(`id`),0)
      FROM `catalog`
    );
    IF ParentId = 0 THEN
      SET ParentId = NULL;
    END IF;
    INSERT INTO `catalog` (`parent_id`) VALUES (ParentId);
    SET i = i + 1;
  UNTIL NOT i < rowCount END REPEAT;
END//
DELIMITER ;

CALL fill__catalog(3000);



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

Код: sql
1.
2.
3.
4.
5.
SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
  FROM `catalog` c
  WHERE Find_in_set(c.`parent_id`, @branch)
    AND NOT Find_in_set(c.`id`, @branch)
  ORDER BY `branch` DESC LIMIT 1



Как видно, на моем домашнем железе запрос отработал за 16 миллисекунд.
/* 0 rows affected, 1 rows found. Duration for 1 query: 0,016 sec. */

Выводы?
...
Рейтинг: 0 / 0
21.02.2013, 16:26
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38161044
DBConstructor
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DBConstructor
Участник
Надо только задать интересующих предков в переменной @branch. К примеру:
Код: sql
1.
  SET @branch = '3';
...
Рейтинг: 0 / 0
21.02.2013, 16:32
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38161406
DBConstructor
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DBConstructor
Участник
Arhat109DBConstructor,

протестил:

1. Таблица 10 деревьев по 1 листу в уровне, всего 300 уровней (3000 записей всего!)
2. Решение Бочкова дает выборку от 0,5 до 1 сек.
3. Решение с составным индексом (моё тут последнее) дает 50-80мсек.
4. Ваше решение проработало больше (уже 705сек и ещё пашет)... сколько точно - не знаю.

как-то так. :)

У нас не получится повторить опыты друг друга, ввиду слишком разных условий их проведения.

Попробуй на своей таблице, с одинаковыми для предыдущих тестов условиями, следующий вариант:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
SET @branch = ?;
SELECT @exists:=EXISTS (
    SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
      FROM `catalog` c
      WHERE Find_in_set(c.`parent_id`, @branch)
        AND NOT Find_in_set(c.`id`, @branch)
      ORDER BY `branch` DESC LIMIT 1)
  FROM `catalog`
  WHERE @exists;



Результат будет в переменной @branch
...
Рейтинг: 0 / 0
21.02.2013, 20:24
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38161438
DBConstructor
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DBConstructor
Участник
Немного усложнил свой вариант, чтобы чуть-чуть сравнять условия опыта, и прогнал оба алгоритма:

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
-- by DBConstructor
SET @branch='1';
SET @exists = 1;
SELECT `id`
  FROM `catalog`, (
    SELECT @branch as branch, @exists:=EXISTS (
      SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
        FROM `catalog` c
        WHERE Find_in_set(c.`parent_id`, @branch)
          AND NOT Find_in_set(c.`id`, @branch)
        ORDER BY `branch` DESC LIMIT 1) rowsExists
    FROM `catalog`
    WHERE @exists
    ORDER BY `branch` DESC LIMIT 1) as branch
  WHERE Find_in_set(`id`, `branch`.`branch`)
/* 0 rows affected, 1 667 rows found. Duration for 3 queries: 0,390 sec. */


-- by Bochkov
SET @a='1';
SELECT id FROM(
    SELECT @index:=INSTR(@a,',') as coma_index,
        @id:=SUBSTRING_INDEX(@a, ',', 1)  as id,
        @a:=SUBSTRING(@a,IF(@index,@index+1,0)),
        @a:=CONCAT_WS(IF(LENGTH(@a)>0,',',''),@a,
        (SELECT group_concat(id)
           FROM `catalog`
           WHERE parent_id=@id)) as array
      FROM `catalog`
      WHERE LENGTH(@a)>0) childs;
/* 0 rows affected, 1 667 rows found. Duration for 2 queries: 1,575 sec. */



Первый алгоритм отработал в 4 раза быстрее.
...
Рейтинг: 0 / 0
21.02.2013, 21:09
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38162967
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
DBConstructorArhat109DBConstructor,

протестил:

1. Таблица 10 деревьев по 1 листу в уровне, всего 300 уровней (3000 записей всего!)
2. Решение Бочкова дает выборку от 0,5 до 1 сек.
3. Решение с составным индексом (моё тут последнее) дает 50-80мсек.
4. Ваше решение проработало больше (уже 705сек и ещё пашет)... сколько точно - не знаю.

как-то так. :)

У нас не получится повторить опыты друг друга, ввиду слишком разных условий их проведения.

Попробуй на своей таблице, с одинаковыми для предыдущих тестов условиями, следующий вариант:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
SET @branch = ?;
SELECT @exists:=EXISTS (
    SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
      FROM `catalog` c
      WHERE Find_in_set(c.`parent_id`, @branch)
        AND NOT Find_in_set(c.`id`, @branch)
      ORDER BY `branch` DESC LIMIT 1)
  FROM `catalog`
  WHERE @exists;



Результат будет в переменной @branch

Только сегодня заметил.
В переменной @branch оказывается только исходное значение "3" за 46мсек. Увы.
...
Рейтинг: 0 / 0
22.02.2013, 23:58
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38162973
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
Тут приведен код тестового примера и результаты сравнений:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
# test(in integer search_num) {
BEGIN

SET @C='Special create table for ver.2: with composed primary key';
DROP TABLE IF EXISTS `tree`;
CREATE TABLE IF NOT EXISTS `tree` (
   `level`     int(11)          NOT NULL
  ,`parent_id` int(11) unsigned NOT NULL
  ,`id`        int(11) unsigned NOT NULL # auto_increment
  ,`data`      varchar(255) character set 'utf8' default ''
  ,PRIMARY KEY  (`level`,`parent_id`,`id`)
#  ,UNIQUE KEY `id` (`id`) -- for autoincrement needs!
  ,KEY `parent_id` (`parent_id`)
  ,KEY `id`        (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

SET @C='Inserting tree into table';
SET @depth = 10;
SET @maxLevel = 300;

SET @level = 0;
REPEAT
  SET @d = 1;
  REPEAT
    INSERT INTO `tree` SET
        `level`     = @level
      , `parent_id` = @parent:=IF(@level=0, 0, @d + (@level-1) * @depth) #FLOOR( RAND()*@level*@depth ) )
      , `id`        = @d + @level * @depth
      , `data`      = CONCAT('data for parent = ',@parent)
    ;
    SET @d = @d + 1;
  UNTIL @d > @depth END REPEAT;
  SET @level = @level + 1;
UNTIL @level > @maxLevel END REPEAT;
COMMIT;

SET @C='Ver.1: with subquery for each childs... correct for simple query and any tables but stuppid...';
SELECT
  @idx := CAST(SUBSTRING_INDEX(@array, ',', 1) AS SIGNED) AS idx
  , @array := CONCAT_WS(
          IF(LENGTH(@array) > LENGTH(@idx), ',', '')
          , SUBSTRING(@array, CHAR_LENGTH(@idx)+2)
          , (SELECT GROUP_CONCAT(`id`) FROM `tree` WHERE `parent_id` = @idx)
  ) AS array
FROM (SELECT @array:=CONCAT('',search_num), @idx:=0) AS dummy
, `tree` AS ch
WHERE
  LENGTH(@array) > 0
;
# selected=301 items by 0.59 .. 0.61sec. (10 times).

SET @C='Ver.2: table must composed primary key (level, parent_id, id)... quickly,  full index scan...';
SELECT
  ch.`level` AS LEVEL
  , IF( @pr<>ch.`parent_id`, GREATEST(
        @array:=REPLACE(@array, @prc, '')
        , @prc:=CONCAT(',',ch.`parent_id`,',')
        , @pr:=ch.`parent_id`
    ), @pr) AS parent
  , GREATEST(ch.`id`
    , IF( LOCATE(@prc, @array) > 0
        , @array := CONCAT(@array, CONCAT(',',ch.`id`,','))
        , ''
  )) AS childs
FROM (SELECT @prc:=@array:=CONCAT(',',@pr:=search_num,',')) AS dummy
, `tree` AS ch FORCE INDEX (`PRIMARY`) # if present other index!
WHERE LOCATE( CONCAT(',',ch.`parent_id`,','), @array) > 0;
# selected=300 items by 0.21 .. 0.8 sec.


SET @branch=CONCAT('', search_num);
SELECT @branch as branch
  FROM `tree`
  WHERE EXISTS (SELECT 
         @branch:=CONCAT_WS(',', @branch, GROUP_CONCAT(`id`)) branch
       FROM `tree`
       WHERE FIND_IN_SET(`parent_id`, @branch)
         AND NOT FIND_IN_SET(`id`, @branch)
       GROUP BY `parent_id`
       ORDER BY `branch` DESC LIMIT 1)
  ORDER BY `branch` DESC LIMIT 1;
#selected=string by 2min 15sec. (one time starting index was added)


SET @branch = CONCAT('', search_num);
SELECT @exists:=EXISTS (
    SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
      FROM `tree` c
      WHERE Find_in_set(c.`parent_id`, @branch)
        AND NOT Find_in_set(c.`id`, @branch)
      ORDER BY `branch` DESC LIMIT 1)
  FROM `tree`
  WHERE @exists;
SELECT @branch;
# selected by 0.046sec, but only 1 result: @branch = '3' (one result only!);


SET @branch=CONCAT('', search_num);
SET @exists = 1;
SELECT `id`
  FROM `tree`, (
    SELECT @branch as branch, @exists:=EXISTS (
      SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
        FROM `tree` c
        WHERE Find_in_set(c.`parent_id`, @branch)
          AND NOT Find_in_set(c.`id`, @branch)
        ORDER BY `branch` DESC LIMIT 1) rowsExists
    FROM `tree`
    WHERE @exists
    ORDER BY `branch` DESC LIMIT 1) as branch
  WHERE Find_in_set(`id`, `branch`.`branch`)
;
# selected=301 items by 0.398sec (three time starting)

END
...
Рейтинг: 0 / 0
23.02.2013, 00:05
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38162975
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
Arhat109,

была слеплена такая вот процедура, в которой ненужный код (на момент проверки) просто тупо комментился.
...
Рейтинг: 0 / 0
23.02.2013, 00:07
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38162978
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
Arhat109,

Во втором примере очепятка, следует читать 0.021 .. 0.08 sec. Неправильно перевел 21 .. 80 миллисекунд в секунды. :)
...
Рейтинг: 0 / 0
23.02.2013, 00:09
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38162982
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
Arhat109,

последний пример запускался три раза с одним временным результатом.
...
Рейтинг: 0 / 0
23.02.2013, 00:11
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38162983
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
Arhat109,

Лицензионное соглашение короткое: "Пользуйтесь на здоровье!" :)
...
Рейтинг: 0 / 0
23.02.2013, 00:12
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38163006
DBConstructor
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DBConstructor
Участник
Arhat109Только сегодня заметил.
В переменной @branch оказывается только исходное значение "3" за 46мсек. Увы.

Я малость тупанул. Забыл написать, что после "SET @branch = ..." надо еще "SET @exists = 1;"
В конечном варианте:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
SET @branch = ?;
SET @exists = 1;
SELECT @exists:=EXISTS (
    SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
      FROM `catalog` c
      WHERE Find_in_set(c.`parent_id`, @branch)
        AND NOT Find_in_set(c.`id`, @branch)
      ORDER BY `branch` DESC LIMIT 1)
  FROM `catalog`
  WHERE @exists;
...
Рейтинг: 0 / 0
23.02.2013, 00:48
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38163014
DBConstructor
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DBConstructor
Участник
Развитие темы Bochkov'а с небольшим увеличением производительности:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
SET @fifo = ?;
SELECT `id` FROM (
  SELECT
      @id:=Cast(Substring_index(@fifo, ',', 1) AS UNSIGNED INTEGER) as id,
      @fifo_len:=Length(@fifo)-Length(@id)-1 as fifo_len,
      @fifo:=Concat_ws(',', If(@fifo_len > 0, Right(@fifo, @fifo_len), NULL),
           (
            SELECT Group_concat(`id`)
              FROM `catalog`
              WHERE `parent_id`=@id
           )) as fifo
    FROM `catalog`
    WHERE Length(@fifo) > 0) branch
...
Рейтинг: 0 / 0
23.02.2013, 01:00
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38163062
DBConstructor
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DBConstructor
Участник
И наконец, самое быстрое решение - решение "молния":

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
SET group_concat_max_len = 65533;
SET character_set_connection = latin1;
SET @seq = '3';
SET @next_seq = NULL;
SELECT `id`
  FROM (
    SELECT
        @id:=Cast(Substring_index(@seq, ',', 1) AS UNSIGNED INTEGER) as id,
        @seq_len:=Length(@seq)-Length(@id)-1 as seq_len,
        @next_seq:=IfNull(If(@seq_len > 0, @next_seq, NULL),
           (
            SELECT Group_concat(`id`)
              FROM `catalog`
              WHERE Find_in_set(`parent_id`, IfNull(@next_seq, @seq))
           )
        ) as next_seq,
        @seq:=If(@seq_len > 0, Right(@seq, @seq_len), IfNull(@next_seq,'')) as seq
    FROM `catalog`
    WHERE Length(@seq) > 0) branch;



Как говорится, ENJOY!
...
Рейтинг: 0 / 0
23.02.2013, 02:39
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38163105
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
DBConstructor,

Потестил в той куче данных: selected = 301 items by 0.7 .. 0.93 sec. Нисколько оно не "скоростной вариант". Точно такой же. :)

1. Справедливости ради: тема - моя и работают у меня эти запросы уже больше года, Бочков самостоятельно(!) нашел решение, которое я тогда не мог выложить. И самое быстрое решение - это:

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
SET @C='Ver.2: table must composed primary key (level, parent_id, id)... quickly,  full index scan...';
SELECT
  ch.`level` AS LEVEL
  , IF( @pr<>ch.`parent_id`, GREATEST(
        @array:=REPLACE(@array, @prc, '')
        , @prc:=CONCAT(',',ch.`parent_id`,',')
        , @pr:=ch.`parent_id`
    ), @pr) AS parent
  , GREATEST(ch.`id`
    , IF( LOCATE(@prc, @array) > 0
        , @array := CONCAT(@array, CONCAT(',',ch.`id`,','))
        , ''
  )) AS childs
FROM (SELECT @prc:=@array:=CONCAT(',',@pr:=search_num,',')) AS dummy
, `tree` AS ch FORCE INDEX (`PRIMARY`) # if present other index!
WHERE LOCATE( CONCAT(',',ch.`parent_id`,','), @array) > 0;
# selected=300items by 0.021 .. 0.080 sec.



Кстати, почему вы так любите Find_in_set()? LOCATE() -- существенно быстрее. :)
...
Рейтинг: 0 / 0
23.02.2013, 10:16
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38163207
DBConstructor
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DBConstructor
Участник
Arhat109DBConstructor,

Потестил в той куче данных: selected = 301 items by 0.7 .. 0.93 sec. Нисколько оно не "скоростной вариант". Точно такой же. :)

1. Справедливости ради: тема - моя и работают у меня эти запросы уже больше года, Бочков самостоятельно(!) нашел решение, которое я тогда не мог выложить. И самое быстрое решение - это:
Я надеюсь, ты не запретишь мне писать в твою тему? ;)
И кстати, самое универсальное и быстрое решение - решение с курсором в SP ( 13935415 ).

У меня никак не получается получить идентичный результат, хотя бы по количеству результирующих строк.
(для тестирования использую сгенерированную таблицу в 3к строк из 13962137 )
Я правильно запускаю твой алгоритм?
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
SET @search_num:='2';
SELECT
--    ch.`level` AS lvl,
    If(@pr<>ch.`parent_id`,
      Greatest(@array:=REPLACE(@array, @prc, ''),
        @prc:=Concat(',',ch.`parent_id`,','),
        @pr:=ch.`parent_id`),
      @pr) AS parent,
    Greatest(ch.`id`,
		  If(Locate(@prc, @array) > 0,
        @array:=Concat(@array, Concat(',',ch.`id`,',')),
        '')
    ) AS childs
  FROM (
        SELECT @prc:=@array:=Concat(',',@pr:=@search_num,',')
      ) AS dummy,
      `catalog` AS ch -- FORCE INDEX (`PRIMARY`) # if present other index!
  WHERE Locate(Concat(',',ch.`parent_id`,','), @array) > 0;


результат его работы:
Код: xml
1.
/* 0 rows affected, 50 rows found. Duration for 2 queries: 0,000 sec. */


50 строк!

А это результат работы алгоритма из 13969815 при SET @seq:='2'; :
Код: xml
1.
/* 0 rows affected, 1 274 rows found. Duration for 5 queries: 0,109 sec. */


1274 строки и на 30% быстрее SP с курсором!

Arhat109Кстати, почему вы так любите Find_in_set()? LOCATE() -- существенно быстрее. :)
1. Этой функции есть куда расти. В будущем, к примеру, она может быть оптимизирована для использования индексов при выборке строк.
2. Меня полностью устраивает её функционал - быстрая, не требуется дополнительного приобразования строк поиска. Можешь сам в этом убедиться:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
SET group_concat_max_len = 65533;
SET @branch = '2';
SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
  FROM `catalog` c
  WHERE Find_in_set(c.`parent_id`, @branch)
    AND NOT Find_in_set(c.`id`, @branch)
  ORDER BY `branch` DESC LIMIT 1
/* 0 rows affected, 1 rows found. Duration for 2 queries: 0,078 sec. */

SET @branch = '2';
SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
  FROM `catalog` c
  WHERE Locate(Concat(',', c.`parent_id`), Concat(',', @branch))
    AND NOT Locate(Concat(',', c.`id`), Concat(',', @branch))
  ORDER BY `branch` DESC LIMIT 1
/* 0 rows affected, 1 rows found. Duration for 2 queries: 0,156 sec. */


Вот как-то так...
...
Рейтинг: 0 / 0
23.02.2013, 16:09
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38163296
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
DBConstructor,

Эта - не "моя" тема. Это фак. И думаю, сюда полезно выкладывать УЖЕ работающие варианты...

Странно что не получается.
Вот тут: 13969570 полностью приведен весь код, которым тестю. В т.ч. и по построению таблицы. Закрываешь комментами, чего не надо и запускаешь. Он оформлен в виде хранимки search_num - её параметр, который указывается при запуске. Я гоняю через EMS-manager, поэтому не трудно скорректировать код процедуры и перекомпилять заново.
...
Рейтинг: 0 / 0
23.02.2013, 19:22
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38163297
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
DBConstructor,

нет НЕ правильно. Посмотрите внимательно. Там нужно дополнительное поле level и составной уникальный ключ. Посмотрите мой тестовый код внимательнее. Это ключевое расширение.
...
Рейтинг: 0 / 0
23.02.2013, 19:24
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38163305
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
Arhat109,

кстати, это вариант с вырезанием найденных узлов ... ежели ничего не резать, то всё резко упрощается до этого:

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
SELECT
  ch.`id` AS child, ch.`parent_id` AS parent, ch.`level` AS level
  , @array := CONCAT(@array, CONCAT(',',ch.`id`,',')) AS array
FROM (SELECT @array:=',9,') AS dummy
, `tree1` AS ch  FORCE INDEX (level)
WHERE
  LOCATE(CONCAT(',',ch.`parent_id`,','), @array) > 0
;
--# индекс: `level` (`level`,`parent_id`,`id`) лучше делать единственным и первичным ключом таблицы
--# тогда можно не прибивать гвоздями...
--# В этом случае надо забыть про автоинтремент, требующий собственного отдельного индекса...



, приведено тут: 13674855
...
Рейтинг: 0 / 0
23.02.2013, 19:40
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38321675
Диклевич Александр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Диклевич Александр
Участник
Вот еще нашел презентацию с описанием разных подходов и их недостатков, с примерами.
Лично мне понравилось решение с помощью Closure Tables.
...
Рейтинг: 0 / 0
05.07.2013, 12:02
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38321799
tanglir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tanglir
Участник
Диклевич АлександрЛично мне понравилось решение с помощью Closure Tables.Это тот же Adjacency list, только с доп. информацией о путях.
Кстати. На 69-м слайде для этой структуры указано Query child - Easy? ЯНХНП.
Если длины пути нет, то задача выборки прямого потомка ("child" же, не "children") в CT наоборот весьма сложна.
Если длина пути есть, то замаешься при добавлении листа вычислять длины путей от всех предков - речь ведь идёт о добавлении листа за один-два запроса без всяких там рекурсий или хранимок, так?Я уж молчу про перенос ветки куда-нибудь в другую часть дерева.

Ну и ещё меня пугает O(n 2 ). Хотя для малых деревьев это и неважно.
...
Рейтинг: 0 / 0
05.07.2013, 13:20
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38342943
deblogger
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
deblogger
Участник
Arhat109-, Проблемы вызывает поиск ВСЕХ потомков от заданного узла. Типовые, предлагаемые решения через последовательные JOIN и UNION -- или громоздки в построении, или предполагают знание или ограничение уровней вложенности.

Уровень вложенности можно хранить в дереве или отслеживать по FK.

В самом первом сообщении написано так, будто бы добавление FK в таблицу обеспечивает легкость процитированного следом запроса. Вполне ясно что FK тут не при чем, запрос совершенно обычный, но я подумал что наверняка эти внешние ключи можно поддержать в приложении и реально обеспечить автоматизм объединений.

Поскольку тема в FAQ вопрос такой. Я добавляю FK к уже готовой таблице, но в information_schema таблица REFERENTIAL_CONSTRAINTS (или типа того) остается пустой.

Драйвер MyISAM. Я знаю там FK смысла не имеют, но информация о них должна сохраняться в БД. Вдруг я захочу привод поменять.

Так вот, где эти ключи отыскать в БД, чтобы через API заюзать?

---

По деревьям. Долго скрипел извилинами и вроде понял что применительно к большинству случаев деревья только способ отображения информации, а не способ ее хранения. Например типичная гармошка Категория-суб-товар-аксессуар на самом деле может тупо указывать на вхождения в одной и той же таблице где все хранится вперемешку. При этом Категория вообще никуда не указывает, а лишь открывает все что в нее входит. Суб может поступить точно так же. В общем пока до товара какого-нибудь не доберешься - ничего не увидишь. Вполне понятно что описать дерево менюшек nested set позволит очень легко и просто.

А чтобы оценить масштабы бедствия с хранением деревьев я бы посоветовал читателям эту статью http://en.wikipedia.org/wiki/Bill_of_materials

OFF Испытываю чувство вины за нацию - ссылки на русскую секцию википедии эта статья не имеет. А вроде бы индустриальная держава были.
...
Рейтинг: 0 / 0
24.07.2013, 22:52
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38342948
deblogger
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
deblogger
Участник
То есть я конечно читал "For storage engines other than InnoDB, MySQL Server parses the FOREIGN KEY syntax in CREATE TABLE statements, but does not use or store it." но логики не могу просечь. На самом деле что ли не сохраняются FK если не выбран привод InnoDB?

А если я выберу этот привод, сделаю FK, а потом поменяю привод - FK сотруться что ли?
...
Рейтинг: 0 / 0
24.07.2013, 23:04
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38342963
deblogger
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
deblogger
Участник
Проверил. Создал в иннодб, в соответствующей таблице в информационной схеме все красиво нарисовалось - какая таблица, какой реф, какие ключи - в общем все есть.

Однако при попытке поменять мотор появляется сообщение, которого и следовало ожидать:

#1217 - Cannot delete or update a parent row: a foreign key constraint fails

Это что, FK проприети Инны? В общем облом.
...
Рейтинг: 0 / 0
24.07.2013, 23:35
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38380705
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
deblogger, перечитал на три раза, но так и не понял, что Вы хотели спросить "на самом деле"... увы.

1. Приведённая Вами цитата имеет отношение к типовым решениям вопроса в данной архитектуре хранения. А именно, при выборке потомков всех уровней от заданного узла - возникает проблема, когда глубина уровней не известна заранее: невозможно построить запрос на "самоджойнах", только потому, что неизвестно сколько их надо джойнить. И только. Там (и тогда я не имел права писать по-другому) был только намек на то, что эта задача имеет решение, которое озвучил Бочков, и по факту его публичного первенства, далее его решение я везде называл его именем (несмотря на то, что у меня оно работало на полгода-год раньше, а у кого-нибудь может и того раньше)... тут оно опубликовано Бочковым - первым.

К вопросам далее - приведенная цитата или не имеет отношения совсем или я не очень понял ход вашего высказывания...

2. FK - это данные движка InnoDb, и правильно, никакого отношения к MyISAM (который и не движок вовсе!) - отношения не имеют. И мускуль совершенно корректно матерится на попытку с установленным FK сменить движок... что Вы нашли "удивительного", а самого интересное - зачем такое надо ... увы непонятно.

3. Параграф о долгом скрипении извилинами - тоже остался непонятным, могу только добавить, что данные в БД "пихаются" в основном чтобы их потом оттудова извлекать и что-то с ними делать... деревья "в целом" применяются не только к данным типа "категория"-"подкат-я"-"товар"... но и много где ещё.

Из всех представленных и обсужденных вариантов, у меня Nested Sets - оказался самым медленным (даже после разборок с ним)... он вообще, годится только для обработок небольших объемов данных, типа "меню"-"подменю" и сильным ограничением на глубину и вествистость структур. Его реальная полезность больше маркетинговая чем программистская. ИМХО конечно.
...
Рейтинг: 0 / 0
29.08.2013, 11:04
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38380763
tanglir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tanglir
Участник
Arhat109И мускуль совершенно корректно матерится на попытку с установленным FK сменить движок... что Вы нашли "удивительного"Хм, почему это корректно? Если объявление ФК (пусть и не работающих) допускается в других движках, то имхо логично было бы как раз НЕ материться на попытку сменить движок.
...
Рейтинг: 0 / 0
29.08.2013, 11:30
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38381229
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
tanglir,

?!? яж не смотрел конкретно этот случай и кто и куда там на самом деле "матерится"... но имхо, если в служебные таблички внесены данные по движке, изменение его далее - некорректно и должно автоматически отслеживаться как нарушение ссылочной целостности... нет? Какая нафиг разница, где нарушается "комплектация ключей" в рабочей базе или служебных табличках... :)
...
Рейтинг: 0 / 0
29.08.2013, 15:23
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38381869
tanglir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tanglir
Участник
Arhat109, глупость состоит в том, что это можно сделать, причём без ошибок ... но в три этапа: убрать фк, сменить движок, добавить фк.
Впрочем, на эту тему надо общаться в другом топике, здесь это вроде как оффтоп :)
...
Рейтинг: 0 / 0
30.08.2013, 05:23
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38381902
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
tanglir,

нельзя. Можно сделать только первые 2 операции. Последняя операция движком MyIsam - не поддерживается. Нет у него FK, и сталобыть "внезапно" - ничего и никуда он добавлять не будет. Просто проигнорит или тоже выдаст обшибку... :)
...
Рейтинг: 0 / 0
30.08.2013, 08:47
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38382011
tanglir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tanglir
Участник
Arhat109росто проигнорит или тоже выдаст обшибку... :)так в том-то и дело, что просто проигнорит! почему тогда "объединённая" операция не игнорит, а ошибку выдаёт? именно этого , насколько я понимаю, и не мог понять deblogger(и я тоже)
...
Рейтинг: 0 / 0
30.08.2013, 10:30
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38384066
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
tanglir,

потому что это не "объединенная операция", а банальный update служебной таблицы, который выдает нарушение содержимого...
...
Рейтинг: 0 / 0
02.09.2013, 13:08
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38530697
Гуляев Гоша
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гуляев Гоша
Участник
Извините все сообщения тут не прочитал и потому может чего-то не в тему скажу.
Я для себя проблему (или задачу) с поиском всех потомков и всех родителей данного узла в дереве делаю с помощью доп. таблицы:
Основная таблица с реализацией дерева
Код: sql
1.
2.
3.
4.
5.
TABLE cat (
 id        INT UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT,
 parentID  INT UNSIGNED NOT NULL,
 catName   CHAR(50) NOT NULL
)



И таблицы в которую вносятся автоматом изменения при изменении данных в таблице cat
Код: sql
1.
2.
3.
4.
5.
6.
TABLE cat_relations (
 id        INT UNSIGNED NOT NULL PRIMARY KEY AUTO_INCREMENT,
 parentID  INT UNSIGNED NOT NULL,
 childID   INT UNSIGNED NOT NULL,
 UNIQUE KEY rel (parentID,childID)
)


В таблицу cat_relation изменения вносятся при каждом внесении изменений в таблицу cat :
Добавление узла node1ID в качестве дочернего узлу node2ID :
Код: sql
1.
2.
3.
4.
5.
6.
7.
INSERT INTO cat_relations (parentID, childID) 
       SELECT aa.parID, node1ID
       FROM    (
           SELECT aa.childID AS parID 
           FROM   cat_relations   AS aa
           WHERE  aa.parentID=node2ID
       ) AS aa


Ну и аналогичным образом удаление ноды и перемещение в другую ноду.
...
Рейтинг: 0 / 0
18.01.2014, 21:51
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38531333
tanglir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tanglir
Участник
Гуляев Гоша, только вот размер доп. таблицы очень быстро растёт . Но для маленьких деревьев прокатит.

Кстати, ЯНП:
Гуляев Гоша Добавление узла node1ID в качестве дочернего узлу node2ID :
Код: sql
1.
2.
3.
4.
5.
6.
7.
INSERT INTO cat_relations (parentID, childID) 
       SELECT aa.parID, node1ID
       FROM    (
           SELECT aa.childID AS parID 
           FROM   cat_relations   AS aa
           WHERE  aa.parentID=node2ID
       ) AS aa

Код: sql
1.
2.
3.
           SELECT aa.childID AS parID 
           FROM   cat_relations   AS aa
           WHERE  aa.parentID=node2ID

выбираем потомков ноды2 и...
Код: sql
1.
2.
3.
INSERT INTO cat_relations (parentID, childID) 
       SELECT aa.parID, node1ID
       FROM (все потомки ноды2)  AS aa


и определяем ноду1 как потомка каждого из потомков ноды2? может, надо было наоборот, предков выбирать?
...
Рейтинг: 0 / 0
20.01.2014, 05:48
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38531335
tanglir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tanglir
Участник
Кстати, похоже, вы изобрели велосипед (или его часть) под названием Closure tables
См. по ссылке здесь 14526689
...
Рейтинг: 0 / 0
20.01.2014, 05:54
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38874046
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
вадя
Участник
немного поделюсь опытом
есть таблица для дерева - по ней надо построить дерево для отобржения на странице HTML
в таблице 354 строки - много это или мало -хз...
таблица обрабатывается в хранимке с рекурсией. и данные заносятся во временную таблицу(в памяти)
отрабатывало ~1сек
для ускорения, в том месте где создаётся эта таблица, создал и ещё одну - копию таблицы из которой строится дерево,
время упало на порядок...только за счёт отказа от дисковых операций
...
Рейтинг: 0 / 0
07.02.2015, 22:26
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38963258
fans74
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
fans74
Участник
mahoune Ссылки:
Моделирование иерархических объектов
// 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

в статье
Моделирование иерархических объектов
http://www.rsdn.ru/article/alg/dbtree.xml

неверно индексы right и left расставлены
правильно тут http://www.ibase.ru/devinfo/DBMSTrees/sqltrees.html - структура идентичная
...
Рейтинг: 0 / 0
19.05.2015, 19:29
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38963264
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
fans74в статье
Моделирование иерархических объектов
http://www.rsdn.ru/article/alg/dbtree.xml

неверно индексы right и left расставленыЧто именно неверно? На глаз ошибок не вижу.
...
Рейтинг: 0 / 0
19.05.2015, 19:39
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38964547
fans74
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
fans74
Участник
miksoftfans74в статье
Моделирование иерархических объектов
http://www.rsdn.ru/article/alg/dbtree.xml

неверно индексы right и left расставленыЧто именно неверно? На глаз ошибок не вижу.

в статье индексы расставлены так:

таб. 1
Id Parent Name Left Right1 0 A1 1 112 1 B1 2 43 1 B2 6 104 2 C1 3 35 3 C2 7 76 3 C3 9 9


Разве не так должно быть?
таб. 2
Id Parent Name Left Right1 0 A1 1 122 1 B1 2 53 1 B2 6 114 2 C1 3 45 3 C2 7 86 3 C3 9 10

в этой статье к примеру ( http://www.woweb.ru/publ/41-1-0-464) обозначены ряд правил:

1. Левый ключ ВСЕГДА меньше правого;
2. Наименьший левый ключ ВСЕГДА равен 1;
3. Наибольший правый ключ ВСЕГДА равен двойному числу узлов;
4. Разница между правым и левым ключом ВСЕГДА нечетное число;
5. Если уровень узла нечетное число то тогда левый ключ ВСЕГДА нечетное число, то же самое и для четных чисел;
6. Ключи ВСЕГДА уникальны, вне зависимости от того правый он или левый;


индексы left и right в таб. 1 этим правилам не удовлетворяют.
...
Рейтинг: 0 / 0
20.05.2015, 18:51
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38964673
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
fans74,

В статье на rsdn используется немного другой набор правил. Благодаря чему соблюдается закономерность "Количество потомков = (Right - Left) / 2".

Собственно, правил может быть много разных. Пожалуй, единственное непременное условие - чтобы числа возрасталали (или убывали) при обходе дерева.
...
Рейтинг: 0 / 0
20.05.2015, 22:36
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38964731
fans74
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
fans74
Участник
miksoftfans74,

В статье на rsdn используется немного другой набор правил. Благодаря чему соблюдается закономерность "Количество потомков = (Right - Left) / 2".

Собственно, правил может быть много разных. Пожалуй, единственное непременное условие - чтобы числа возрасталали (или убывали) при обходе дерева.

ммм.. ясно. Смутило то, что автор статьи ссылается на решения предложенное Joe Celko, а в итоге использует немного другой алгоритм.

Спасибо за разъяснение.
...
Рейтинг: 0 / 0
21.05.2015, 04:32
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #38964825
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
fans74Смутило то, что автор статьи ссылается на решения предложенное Joe Celko, а в итоге использует немного другой алгоритм.Вполне допускаю, что Joe Celko мог предлагать разные правила в в своих разных работах или их разных изданиях. Мысль же не стоит на месте. Можно проверить, если найти первоисточники.
...
Рейтинг: 0 / 0
21.05.2015, 09:08
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #39546829
Ролг Хупин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ролг Хупин
Участник
miksoftfans74Смутило то, что автор статьи ссылается на решения предложенное Joe Celko, а в итоге использует немного другой алгоритм.Вполне допускаю, что Joe Celko мог предлагать разные правила в в своих разных работах или их разных изданиях. Мысль же не стоит на месте. Можно проверить, если найти первоисточники.

Методы, предложенные Joe Celko работают не для всех случаев, только для специальных.
...
Рейтинг: 0 / 0
02.11.2017, 16:52
| Ответить | Цитировать | Написать  
FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
    #39604109
Arhat109
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arhat109
Участник
В связи с развитием Мускуля и наличия далеко продвинутых форков типа МарияДБ предлагаю или обновить тему или указать, что найденные тут решения уже неактуальны. :)
...
Рейтинг: 0 / 0
19.02.2018, 12:54
| Ответить | Цитировать | Написать  
78 сообщений из 78, показаны все 4 страниц
  все  
Форумы / MySQL [игнор отключен] [закрыт для гостей] / FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru             Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=47&tid=1830048]:
 0ms
get settings:
 11ms
get forum list:
 15ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 29ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 103ms
get tp. blocked users:
 2ms
others: 241ms
total:  423ms
созд. / загр.: 423ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]