Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 108
Гм, вариация на тему materialized path. Просто информацию о пути вы разложили на несколько записей.
согласен, я так и написал, что больше всего похоже на materialized path. Но, в отличии от materialized path база работает с числовыми индексами. Плюс, materialized path или ограничен длиной, или поле text, что тоже есть минусом. Несмотря на то, что способ похож на materialized path, я бы не назвал его вариаций.
Ведь materialized path тоже своего рода вариация Adjacency List. ;)
Ведь materialized path тоже своего рода вариация Adjacency List. ;)
Не совсем так.
Вопрос не в том КАК мы храним (запись, текстовое поле или что-то другое), вопрос в том ЧТО мы храним. А мы, по сути, храним полный путь к ноде.
В AL хранятся только две соседних ноды.
Вопрос не в том КАК мы храним (запись, текстовое поле или что-то другое), вопрос в том ЧТО мы храним. А мы, по сути, храним полный путь к ноде.
В AL хранятся только две соседних ноды.
Этот способ требует другого подхода в программировании, этот способ имеет другие недостатки и другие преимущества по сравнению с MP. Единственное, что у этого способа похожи идеи.
Храним мы иерархическую структуру. Любым способом. Разница как раз к том, как храним.
Не вижу смысла продолжать этот разговор, ведь это больше вопрос философии, чем программирования.
ЧТО мы храним
Храним мы иерархическую структуру. Любым способом. Разница как раз к том, как храним.
Не вижу смысла продолжать этот разговор, ведь это больше вопрос философии, чем программирования.
Кстати, а какие сложности с хранением MP в текстовых полях?
размер от 2^16 до 2^32
Хотя хватит и банального VARCHAR на пару-тройку тысяч байт.
Выборка поддерева, кстати, тоже делается 1м запросом.
размер от 2^16 до 2^32
Хотя хватит и банального VARCHAR на пару-тройку тысяч байт.
Выборка поддерева, кстати, тоже делается 1м запросом.
А вы это поле делаете индексом, или нет? Как у вас в таблице на 100000 строк происходит поиск поддерева?
Как вы думаете, почему MP не стал таким популярным, как AL и NS? Я сам думал именно о MP, пока не открыл для себя этот способ.
Как вы думаете, почему MP не стал таким популярным, как AL и NS? Я сам думал именно о MP, пока не открыл для себя этот способ.
Конечно делается индексом. Вы же собираетесь по нему искать.
Записи у вас плодятся неимоверно. Для небольшого форума это может и не критично… но дальше будет хуже
Общее число записей считается по формуле (n+1)*n/2
Каждый последующий элемент будет занимать в (n^2 + 3*n +2) / (n^2 + n) раз больше.
Для n=100 мы имеем 5050 записей. Я тут видел тред на 900 комментариев, это у нас уже 405450 записей.
В общем можно погонять на вопрос производительности. Но не думаю, что ваш способ быстрее.
Записи у вас плодятся неимоверно. Для небольшого форума это может и не критично… но дальше будет хуже
Общее число записей считается по формуле (n+1)*n/2
Каждый последующий элемент будет занимать в (n^2 + 3*n +2) / (n^2 + n) раз больше.
Для n=100 мы имеем 5050 записей. Я тут видел тред на 900 комментариев, это у нас уже 405450 записей.
В общем можно погонять на вопрос производительности. Но не думаю, что ваш способ быстрее.
Формула недостаточно корретна по той причине, что дерево не растёт вглубь.
на 340 объектов у меня получилось 1252 объекта в таблице иерархии.
если бы дерево расло вглубь так, как указано в вашей формуле, то в MP в каждом пути приходилось бы держать и работать с достаточно длинными строками, и я сомневаюсь, что MP показал бы себя в этом лучше, чем FH
на 340 объектов у меня получилось 1252 объекта в таблице иерархии.
если бы дерево расло вглубь так, как указано в вашей формуле, то в MP в каждом пути приходилось бы держать и работать с достаточно длинными строками, и я сомневаюсь, что MP показал бы себя в этом лучше, чем FH
А вы не сомневайтесь, вы замерьте
Основная проблема МП это full-text search в базе.
Если дерево не растет вглубь (ввысь) :) то это трава, а не дерево :)
У вас, похоже, неглубокое дерево. И в вашем случае проблем с поиском не будет даже по текстовым полям.
Они будут расти именно с ростом вложености.
Но тут (в случае стандартного решения) у нас есть обходной маневр. Часть с поиском мы можем возложить не на БД, а на Sphinx например.
Он нам вернет список ID, которые мы уже и используем в запросе к БД.
А в остальном, солидарен с sse. Проведите нагрузочное тестирование разных деревьев способом МП и вашим. И добавьте к топику. Будет более чем интересно :)
Если дерево не растет вглубь (ввысь) :) то это трава, а не дерево :)
У вас, похоже, неглубокое дерево. И в вашем случае проблем с поиском не будет даже по текстовым полям.
Они будут расти именно с ростом вложености.
Но тут (в случае стандартного решения) у нас есть обходной маневр. Часть с поиском мы можем возложить не на БД, а на Sphinx например.
Он нам вернет список ID, которые мы уже и используем в запросе к БД.
А в остальном, солидарен с sse. Проведите нагрузочное тестирование разных деревьев способом МП и вашим. И добавьте к топику. Будет более чем интересно :)
Хотя хватит и банального VARCHAR на пару-тройку тысяч байт.
На счёт этого там тоже, кстати сказано.
Хотя хватит и банального VARCHAR на пару-тройку тысяч байт.
Более того, база не позволяет сделать поле `Path` длиннее 1000 символов
Я немного недопонял. Может, я не ту документацию читаю? Какие тысячи байт в VARCHAR?
В materialized path вообще insert делается 1им запросом.
Преимуществ не увидел — они как-то в статье прописаны?
Преимуществ не увидел — они как-то в статье прописаны?
нууу. для меня преимущества — очевидны.
при выборке работаем с числовым индексом, никак не ограничены в уровне вложенности.
поиск определённого узла будет быстрее: WHERE `ParentID` = 1453 быстрее, чем WHERE `Path` LIKE '%.1453.%' и т.п.
при выборке работаем с числовым индексом, никак не ограничены в уровне вложенности.
поиск определённого узла будет быстрее: WHERE `ParentID` = 1453 быстрее, чем WHERE `Path` LIKE '%.1453.%' и т.п.
Спорное утверждение. Скорость поиска зависит не только от предиката поиска, но еще и от того, сколько строк лежит в таблице. Из статьи совершенно не следует, что выгода от замены предиката на менее трудоемкий превысит потери на поиск в таблице значительно большего размера.
У вас есть конкретные цифры — например, для среднего сбалансированного дерева в 500 элементов со средним числом дочерних item в 4?
У вас есть конкретные цифры — например, для среднего сбалансированного дерева в 500 элементов со средним числом дочерних item в 4?
Должно получиться примерно 500 * 10 записей
теперь есть, читайте)
Почитал.
Странные у вас тесты, и вот почему:
— в жизни вам часто надо извлекать просто рандомный узел?
— вы меряете производительность только операции select. Как насчет insert/update?
Синтетические тесты мало что доказывают, вы бы на сценариях real world потестировали.
Странные у вас тесты, и вот почему:
— в жизни вам часто надо извлекать просто рандомный узел?
— вы меряете производительность только операции select. Как насчет insert/update?
Синтетические тесты мало что доказывают, вы бы на сценариях real world потестировали.
в жизни вам часто надо извлекать просто рандомный узел?Если бы я извлекал не рендомный узел, а какой-то определенный, то меня могли бы обвинить в фальсификации и в том, что я специально выбрал такие числа, на которых более выгоден мой метод. В моих же тестах явно видно — в среднем FH намного быстрее, чем MP
вы меряете производительность только операции select. Как насчет insert/update?Хорошо. Чуть позже — гляну
Синтетические тесты мало что доказывают, вы бы на сценариях real world потестировали.Консольный форум, как уже говорилось, использует именно эту систему. У меня там не подключено кеширование и акселераторы, я хостюсь на дешёвом хостинге за 5 баксов. Генерация страницы занимает чуть меньше, чем 0.02 секунды. При этом форум с лёгкостью выдержал ХабраЭффект и некоторое замедление в работе было вызвано не движком, а недостаточно широким каналом. Движок же отработал с лёгкостью.
Более того, товарищ, который навёл меня на эту мысль (Java-прогер с многолетним стажем) утверждает, что в HighLoad'е, с которым он работал — используется именно этот способ и он очень хорошо себя показывает.
да нормальный тест инсерт/update не нужно вообще мерить, ведь это редкие нарушающие кеш операции
Кгм. А вот такой вопрос зачем у вас
LIKE '%.1453.%'?
Если мы получали этот самый 1453й объект. То у нас должна быть информация о пути к нему.
Например, '1.17.234'
И тогда наш LIKE превратится в что-то вида
LIKE '1.17.234.1453.%';
LIKE '%.1453.%'?
Если мы получали этот самый 1453й объект. То у нас должна быть информация о пути к нему.
Например, '1.17.234'
И тогда наш LIKE превратится в что-то вида
LIKE '1.17.234.1453.%';
а получать список родителей можно вообще без запросов XD
Всем: добавлен пункт «Сравнение данного способа и Materialized Path»
интересный подход! использовали одно время что-то похожее, но число записей переползло за
10 000 000, наш велосипед стал ползать и пересели на HBase =)
используем систему в биллинге одного оператора моб. связи
10 000 000, наш велосипед стал ползать и пересели на HBase =)
используем систему в биллинге одного оператора моб. связи
То, что вы храните в базе, называется транзитивным замыканием графа (дерева, в вашем случае): www.cs.sunysb.edu/~algorith/files/transitive-closure.shtml
Тема не новая, в интернете информации очень много.
Тема не новая, в интернете информации очень много.
Собственно, всё гениальное просто. При необходимости сделал бы скорей всего также.
А не поможет ли кто линкой на статью на эту тему? А то как то грустно, что термины Adjacency List, Nested Set, Materialized Path почти полностью не о чём. Английский тоже подходит.
А не поможет ли кто линкой на статью на эту тему? А то как то грустно, что термины Adjacency List, Nested Set, Materialized Path почти полностью не о чём. Английский тоже подходит.
AL, NS, MP:
habrahabr.ru/blogs/development/46659/
phpclub.ru/faq/Tree/
Про применение FH в php лично я нигде не видел. Ну и почитайте ссылку, что дал tegger деревом выше.
habrahabr.ru/blogs/development/46659/
phpclub.ru/faq/Tree/
Про применение FH в php лично я нигде не видел. Ну и почитайте ссылку, что дал tegger деревом выше.
Более того, база не позволяет сделать поле `Path` длиннее 1000 символов (#1071 — Specified key was too long; max key length is 1000 bytes),
заблуждаетесь
`field` VARCHAR(10000) COLLATE utf8_general_ci DEFAULT NULL,
а про 1000 он говорит совершенно верно — нельзя делать КЛЮЧИ длиннее 1000байт (для myisam)
то есть, вы предлагаете сделать это поле не индексом?
то есть я предлагаю:
1. исправить неточность в статье, которая может смутить неопытных разработчиков
2. делать индексы разумных размеров. индекса в 1000 байт хватит за глаза для любой древовидной структуры, какую я только могу придумать. ну или помогите придумать структуру, для хранения пути которой не хватит 1000 байт. даже если придумаете — ну будет использован префикс в 1000. ну отсечётся 99% не попадающих под условие записей. ну будет сканирование по оставшимся. что страшного?
1. исправить неточность в статье, которая может смутить неопытных разработчиков
2. делать индексы разумных размеров. индекса в 1000 байт хватит за глаза для любой древовидной структуры, какую я только могу придумать. ну или помогите придумать структуру, для хранения пути которой не хватит 1000 байт. даже если придумаете — ну будет использован префикс в 1000. ну отсечётся 99% не попадающих под условие записей. ну будет сканирование по оставшимся. что страшного?
Мне больше жульничество с лайком понравилось.
Искать без левого процента совсем несложно.
Но ведь даст такие неудобные цифры! :)
Искать без левого процента совсем несложно.
Но ведь даст такие неудобные цифры! :)
а как ваш метод поведет себя при перестановке узлов, удалении узла и вставке? что то сомневаюсь, что в этом он будет быстрее
Удаление ветки — операция вообще тривиальная:
Кстати. Не знаю, хорошо ли это, но при изменении иерархии таблица с данными будет совершенно свободна, то есть затрагиваться не будет.
DELETE FROM `Elements`
INNER JOIN `ElementsHierarchy` as `Hier`
ON `Hier`.`ElemID` = `Elements`.`ID`
WHERE `Hier`.`ParentID` = {ID} OR `Elements`.`ID` = {ID}
* This source code was highlighted with Source Code Highlighter.Кстати. Не знаю, хорошо ли это, но при изменении иерархии таблица с данными будет совершенно свободна, то есть затрагиваться не будет.
В Drupal 6 для хранения меню используется вариант Materialized Path, но с ограничением по уровню вложенности. И путь хранится не в одном текстовом поле, а целыми: p1, p2, ..., p9. Еще поле depth.
Ключ сделан по (`menu_name`,`p1`,`p2`,`p3`,`p4`,`p5`,`p6`,`p7`,`p8`,`p9`).
В два селекта вроде можно уложиться достаточно шустрых для получения всех пунктов подменю (сначала определяем путь к нужном пункту меню, а потом селект для выборки потомков).
Ключ сделан по (`menu_name`,`p1`,`p2`,`p3`,`p4`,`p5`,`p6`,`p7`,`p8`,`p9`).
В два селекта вроде можно уложиться достаточно шустрых для получения всех пунктов подменю (сначала определяем путь к нужном пункту меню, а потом селект для выборки потомков).
> Я не встречал в интернете упоминания о нём, о чём очень удивлен
Вы, видимо, совсем не искали.
Ибо, способ чуть моложе вселенной, и применяется часто.
Так же часто и подробно описан.
gsbelarus.com/gs/modules.php?name=News&file=article&sid=314
www.delphikingdom.com/asp/viewitem.asp?catalogid=1263
www.delphikingdom.com/asp/answer.asp?IDAnswer=29168
Вы, видимо, совсем не искали.
Ибо, способ чуть моложе вселенной, и применяется часто.
Так же часто и подробно описан.
gsbelarus.com/gs/modules.php?name=News&file=article&sid=314
www.delphikingdom.com/asp/viewitem.asp?catalogid=1263
www.delphikingdom.com/asp/answer.asp?IDAnswer=29168
Лет 5 назад, когда нужно было сделать дерево, я придумал практически такую же схему (с небольшими, но не принципиальными отличиями). На мой взгляд, она намного проще и приятнее, чем тот же nested tree.
Метод, как выше уже сказано, не то чтобы нов… В общем, он удобен для не очень больших read-only деревьев. Но как только вы захотите менять дерево, вы сразу почувствуете ограничения метода.
Мне на практике нужно примитивное, неглубокое дерево, без 11000 предков и т.п… Уровней 3-4 думаю будет более чем достачно для вменяемых ветвей комментариев. В данном случае чем «деревянней», тем лучше. А все статьи почему то описывают какие то безумства с данными, имеющими весьма посредственное отношение к реалиям(
Ну это я так, погундел немножко.
Ну это я так, погундел немножко.
А как будут обстоять дела с поиском по не ключевым полям? Да еще и с поискам по всем поддеревьям по этим же не ключевым полям. Думаю, что здесь и индекс-то особо не поможет.
А вот в Sql Server есть родная поддержка иерархий.
придумают всё что угодно, лишь бы не CONNECT BY…
а в MySQL есть CONNECT BY?
Пордон, промазал, это ответ на SQL SERVER иерархии
В Oracle есть. И все пытаются сделать тоже самое, но не копировать, а извратиться как-то.
В Oracle есть. И все пытаются сделать тоже самое, но не копировать, а извратиться как-то.
база не позволяет сделать поле `Path` длиннее 1000 символов (#1071 — Specified key was too long; max key length is 1000 bytes), что значит, что, если у нас средняя длина ID будет 4 символов мы не сможем делать деревья глубже 1000/(4+1), то есть самое глубокое возможное дерево в таком случае — 200 элементов. и 166 при средней длине ключа 5 цифр (если на сайте более 50000 комментариев в среднем)
Materialized path можно строить иначе. В таблице, описывающией иерархию будем хранить ссылку на объект (ElemId) и путь (Path).
ElemId, Path
В каждом сегменте пути будем записывать номер узла в поддереве по порядку (а не ElemId). И сделаем размер сегмента пути фиксированной длины (скажем 3 символа), чтобы сортировка по такому пути выдавала нам дерево в естественном порядке.
"000" -- первый уровень
"000000" -- второй уровень
"000001000"
"000001001"
"000002"
"001"
"002"
Уровень узла в таком дереве вычисляется по формуле Level = strlen(path) / 3.
Сейчас в каждом поддере можно создать не более чем 10^3 = 1000 узлов. Но если увеличить основание системы счисления, то емкость дерева возрастет. В php функция base_convert позволяет увеличить базу до 36. Т.е. емкость уже составит 36^3 = 46656. Для комментов этого достаточно. И размер пути получается небольшим. 1000 символов хватит для кодирования 1000/3 = 333 уровней. Ну, а скажем путь к комменту на 20-м уровне составит 20*3 = 60 символов. В MySQL есть аналогичная функция. Поэтому всю математику связанную с пересчетом пути при модификации дерева можно записывать прямо в запросе.
Конкретно под комментарии стратегию создания пути можно еще оптимизировать. Понятно что, чем глубже уровень, тем меньше «ветвистость» комментов. Максимальное число комментов стоит ожидать лишь на первом уровне. Поэтому только у первого сегмента пути оставим длину 3 символа. А остальные сегменты можно сократить и до 2-х. 1296 комментов на подуровне хватит заглаза. Таким образом путь к комменту на 20 уровне будет составлять всего 41 символ.
"000" -- первый уровень
"00000" -- второй уровень (2 символа в сегменте)
"0000100"
"0000101"
"00002"
"001"
"002"
Да, нужно обязательно ограничить длину индекса в таблице MySQL, для поля Path. Это не сильно скажется на производительности, зато позволит прилично сэкономить по памяти.
стыдно признаться, но я не совсем понял, как с этим работать? может, вы напишите статью, где детально распишите этот способ с примерами того, как с ним работать?
Так элементарно же. Path обычный текст. Структура его фиксированна. В данном случае на каждый порядковый номер находящийся на одном уровне отводиться 3 символа. Если использовать только цифры, то на одном уровне может находиться только 1000 узлов.
Т.е. к примеру у элементов на первом уровне (у которых нет предка) коды будут:
000
001
002
003
004
…
А коды для элементов которые являются потомками первого элемента (с Path=000) коды будут:
000001
000002
000003
…
Как и у любого метода тут есть свои тонкости и недостатки. К примеру, если потребуется переместить узел в другое место, а id элементов у нас возрастают последовательно (1, 2, 3 ....), то придется произвести пересчет элементов если новый элемент необходимо подключить первым (а не добаить в конец).
Т.е. к примеру у элементов на первом уровне (у которых нет предка) коды будут:
000
001
002
003
004
…
А коды для элементов которые являются потомками первого элемента (с Path=000) коды будут:
000001
000002
000003
…
Как и у любого метода тут есть свои тонкости и недостатки. К примеру, если потребуется переместить узел в другое место, а id элементов у нас возрастают последовательно (1, 2, 3 ....), то придется произвести пересчет элементов если новый элемент необходимо подключить первым (а не добаить в конец).
Не. Ну суть я понял. Я не понял, как с ним работать. Вот смотри — в тестах я написал функции getTreeByParent_MP и getTreeByParent_FH, которые позволяют одним запросом получить дерево по ID родителя. А как будет выглядеть такая функция для вашего метода? Как будет выглядеть перенос ветки на другое дерево и т.п? Я просто не совсем представляю, как с этим работать. Ну и, тем более, FH не накладывает совершенно никаких ограничений, как я уже говорил. Совершенно никаких.
Все данные по иерархии находятся в Path. Усли у нас есть элемент с 005003010, то для получения всех потомков для родительских элементов нужно будет сделать выборку по вхождения в Path подтроки 005.
Перенос элемента потребует знать Path будующего родителя. Тогда к потребуется узнать максимальный номер его последнего потомка и увеличить его на величину шага. Для ускорения процесса max_id последнего потомка можно хранить в таблице подобно тому, как это делается для auto_increment поля для таблицы. Для всех непосредственных потомков этого узла придется сделать update поля Path. Так что все недостатки данного метода по большей части связанными именно при необходимости кроить дерево.
ЗЫ. Метода не мой, и даже не мною используется, топикстартер данного треда не я ;)
Перенос элемента потребует знать Path будующего родителя. Тогда к потребуется узнать максимальный номер его последнего потомка и увеличить его на величину шага. Для ускорения процесса max_id последнего потомка можно хранить в таблице подобно тому, как это делается для auto_increment поля для таблицы. Для всех непосредственных потомков этого узла придется сделать update поля Path. Так что все недостатки данного метода по большей части связанными именно при необходимости кроить дерево.
ЗЫ. Метода не мой, и даже не мною используется, топикстартер данного треда не я ;)
интересно. спасибо. попробую использовать.
писал нечто подобное — спасибо что осветили тему и тут спасибо коментаторам на доп. материал
Вот чего нету так єто возможности сортировки элементов одного уровня, хотя можно соответствующие поле создать в таблице с данными.
А теперь нужно взять живую, большую, реальную базу и протестировать все методы на все возможные операции — єто будет интересно :)
А теперь нужно взять живую, большую, реальную базу и протестировать все методы на все возможные операции — єто будет интересно :)
Ваш пример из разряда «как любую структуру БД запихнуть две таблицы».
В общем-то, способ очень интересный, но это моделирование БД в самой же БД, потому что примерно таким же способом базы данных и хранят информацию о таблицах и данных внутри себя.
Ваш метод интересен, но помоему совершенно не практичен для сложных структурированных БД, потому что вы не сможете писать сложные запросы, крестить и пересекать таблицы и т.д., а для больших задач тысячей мелких selectов не обойдетесь…
ИМХО.
В общем-то, способ очень интересный, но это моделирование БД в самой же БД, потому что примерно таким же способом базы данных и хранят информацию о таблицах и данных внутри себя.
Ваш метод интересен, но помоему совершенно не практичен для сложных структурированных БД, потому что вы не сможете писать сложные запросы, крестить и пересекать таблицы и т.д., а для больших задач тысячей мелких selectов не обойдетесь…
ИМХО.
опечатка: «как любую структуру БД запихнуть В две таблицы»
Вы уж простите, но я не совсем вас понял.
Давайте начнём с того: какой способ вы предлагаете для хранения иерархических структур и чем этот способ лучше представленного в статье.
Объясните также — что мне мешает писать сложные запросы в данном примере? Для меня удивительно такое заявление.
Зачем мне тысячи мелких select'ов?
Давайте начнём с того: какой способ вы предлагаете для хранения иерархических структур и чем этот способ лучше представленного в статье.
Объясните также — что мне мешает писать сложные запросы в данном примере? Для меня удивительно такое заявление.
Зачем мне тысячи мелких select'ов?
Извините, я не хотел делать громких заявлений и шокировать вас. Честно говоря, я перед этим прочитал еще одну статью, а когда увидел вашу, она показалась очень схожа и я подумал что это примерно тоже самое, не особо вчитываясь. Так что приношу свои извинения относительно фразы «как любую структуру БД запихнуть В две таблицы».
Но все-таки остается вопрос: почему не обойтись одной таблицей elements:
id, parentid, parentlevel, data?
Но все-таки остается вопрос: почему не обойтись одной таблицей elements:
id, parentid, parentlevel, data?
если сделать одну таблицу, то parentlevel не нужен, так как в parentid мы можем записать айди единственного элемента. — ближайшего и parentlevel будет у него 1. Если я правильно понял, о чём вы. Этот способ самый известный и логичный, и называется Adjacency List и его главный недостаток — выборка всего дерева начиная от определенной ветки, так как надо выбирать дерево рекурсивно, или другим способом — так же не очень производительным. Этот способ достаточно известен и в интернете можно найти список его недостатков)
Наверное, Вы не совсем поняли меня.
Я понимаю что parentlevel не нужен, но если его добавить, то пример ни чем отличается от вашего.
В parentlevel просчитывается уровень вложенности элемента, тогда чтобы показать все элементы 2 уровня надо буде написать:
SELECT * FROM table WHERE parentlevel=2;
и тем самым не нужно рекурсивно опускаться вниз чтобы досчитать до какого-то уровня.
Я понимаю что parentlevel не нужен, но если его добавить, то пример ни чем отличается от вашего.
В parentlevel просчитывается уровень вложенности элемента, тогда чтобы показать все элементы 2 уровня надо буде написать:
SELECT * FROM table WHERE parentlevel=2;
и тем самым не нужно рекурсивно опускаться вниз чтобы досчитать до какого-то уровня.
Я понимаю что parentlevel не нужен, но если его добавить, то пример ни чем отличается от вашего.
Если вы так говорите, значит вы или не читали статью, или читали её невнимательно.
чтобы показать все элементы 2 уровня надо буде написать:
Да, но так вы получите только один уровень. Но как получить всё дерево под определенным элементом?
В способе, который предложен в сабже ключевое не уровень элемента, а список ID всех родителей. Таким образом, выбрав определенный ID мы можем простым поиском по индексам найти список всех его детей, независимо от уровня вложенности.
Перепутал, коммент стер
вложенные множества чем не угодили?
я думаю, что все здесь знают о недостатках Nested Sets. Кто-то с этими недостатками смирился, но меня они — не устраивают. Особенно, по той причине, что есть альтернатива лучше.
А еще есть Netsted Intervals, у которых этих недостатков меньше, благодаря тому, что left и right задаются рациональными числами. Статья:
www.dbazine.com/oracle/or-articles/tropashko4, математика: arxiv.org/abs/0806.3115v1
www.dbazine.com/oracle/or-articles/tropashko4, математика: arxiv.org/abs/0806.3115v1
какие недостатки тебя не устраивают?
insert/update трудоемки.
А для select возможно даже получше чем MP будет.
А для select возможно даже получше чем MP будет.
Тяжелые вставки. Не говоря уже о перемещениях (хотя, фиг с ними, с перемещениями, это не часто нужно).
В классических netsted sets вставка узла заставляет пересчитывать все правое поддерево. Достаточно даже небольшого количества одновременных запросов пользователей на добавление узла, чтобы база просела. Я имею ввиду, например, комменты.
В классических netsted sets вставка узла заставляет пересчитывать все правое поддерево. Достаточно даже небольшого количества одновременных запросов пользователей на добавление узла, чтобы база просела. Я имею ввиду, например, комменты.
выше есть уже два сообщения по этому поводу. плюс мне не нравится идеология этого метода. я не говорю, что она плохая, я говорю, что она мне не нравится. Не нравится точно так же, как не нравятся суши. Понимаешь о чём я?
и, таки, какие преимущества у NS и NI по сравнению с предложенным в статье способом, кроме того что не используется дополнительная таблица (и преимущество ли это?)
NS славится чертовски легкими select'ами, с поиском по эффективному ключу. NI добавляет легкие вставки.
В предлагаемом (защищаемом? ))) Вами методе:
* для select необходим тяжелый inner join таблицы иерархии самой на себя.
* присутствует бОльшая избыточность. Хотя программно используется лишь один запрос на вставку, база вставляет несколько записей (для которых нужно создать индекс и все это писать на диск).
* Если в колонке таблицы многократно дублируются одни и те же значения, то индексы теряют эффективность.
Все это вместе делает способ представления данных не эффективным.
Не ясно, чем задается прядок узлов в дереве.
Про дополнительную таблицу, простите, не понял…
В предлагаемом (защищаемом? ))) Вами методе:
* для select необходим тяжелый inner join таблицы иерархии самой на себя.
* присутствует бОльшая избыточность. Хотя программно используется лишь один запрос на вставку, база вставляет несколько записей (для которых нужно создать индекс и все это писать на диск).
* Если в колонке таблицы многократно дублируются одни и те же значения, то индексы теряют эффективность.
Все это вместе делает способ представления данных не эффективным.
Не ясно, чем задается прядок узлов в дереве.
Про дополнительную таблицу, простите, не понял…
тяжелый inner join
Объясните, а откуда такая всеобщая боязнь JOIN'ов?
Хотя программно используется лишь один запрос на вставку, база вставляет несколько записей
Почему-то я не сомневаюсь, что в любой СУБД это дело очень хорошо оптимизированно
Если в колонке таблицы многократно дублируются одни и те же значения, то индексы теряют эффективность.
Ммм, какая интересная информация. Пруфлинк?
Не ясно, чем задается прядок узлов в дереве.
При необходимости — еще одним полем в таблице иерархии, по которому осуществляется сортировка
Про дополнительную таблицу, простите, не понял…
В NS и NI, в отличии от FH не создается еще одна таблица, что можно отнести к преимуществам.
использую этот же подход, но не храню уровень ибо count его дает
Я как раз на SEF весной рассказывал про аналогичный метод:
www.slideshare.net/xorets/ss-1493870?type=presentation
Там описан метод обновления таблицы связей, который позволяет вставлять любую связь в любое место. Работает все довольно эффективно, мы используем давно и с удовольствием. Вот здесь все расписано в подробностях:
blogs.byte-force.com/media/p/1148.aspx
www.slideshare.net/xorets/ss-1493870?type=presentation
Там описан метод обновления таблицы связей, который позволяет вставлять любую связь в любое место. Работает все довольно эффективно, мы используем давно и с удовольствием. Вот здесь все расписано в подробностях:
blogs.byte-force.com/media/p/1148.aspx
База не кластеризуется, никаких ухищрений для распределения нагрузки по разным машинам не предпринималось. Я вообще не уверен, что схема типа шардинга может быть с успехом применена в таких условиях. Надо думать.
Схема точно работает хорошо с десятками тысяч объектов. С существенно большим кол-вом (больше 100 тыс) не проверяли. Уровень вложенности — 5-10.
Это точно работает на порядок (как минимум) быстрее, чем алгоритмы с итеративным выбором во временную таблицу. Ибо от них мы и избавлялись. А вот насколько быстрее вообще всех-всех вариантов, да еще и в разных условиях — я не знаю. Был бы рад, если кто-то взял на себя труд проверить.
Схема точно работает хорошо с десятками тысяч объектов. С существенно большим кол-вом (больше 100 тыс) не проверяли. Уровень вложенности — 5-10.
Это точно работает на порядок (как минимум) быстрее, чем алгоритмы с итеративным выбором во временную таблицу. Ибо от них мы и избавлялись. А вот насколько быстрее вообще всех-всех вариантов, да еще и в разных условиях — я не знаю. Был бы рад, если кто-то взял на себя труд проверить.
Можете привести пример запроса для выбора всех узлов (строк), исключая подчиненных для указанного?
Вы забыли написать в явном виде те «три простых запроса», которые нужны добрая добавления узла в дерево.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Full Hierarchy — иерархические структуры в базах данных