ReSQL.ru
     
powered by simpleCommunicator - 2.0.44     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / MySQL [игнор отключен] [закрыт для гостей] / FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
25 сообщений из 78, страница 3 из 4
  3  все
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
| Ответить | Цитировать | Написать  
25 сообщений из 78, страница 3 из 4
  3  все
Форумы / MySQL [игнор отключен] [закрыт для гостей] / FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru             Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=47&msg=38531333&tid=1830048]:
 0ms
get settings:
 11ms
get forum list:
 13ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 33ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 53ms
get tp. blocked users:
 2ms
others: 13ms
total:  145ms
созд. / загр.: 145ms
x
x
Закрыть


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