Comments 22
Вариант с нумерацией есть, например, на сайте РСДН — rsdn.ru/article/db/Hierarchy.xml
Решение интересное, но не учитывает принципы функционирования баз данных и многих предметных областей. Предметные области оставим в покое, а вот принципы функционирования обсудим.
Итак, почему
Решение интересное, но не учитывает принципы функционирования баз данных и многих предметных областей. Предметные области оставим в покое, а вот принципы функционирования обсудим.
Итак, почему
Вариант с нумерацией есть, например, на сайте РСДН — rsdn.ru/article/db/Hierarchy.xml
Решение интересное, но не учитывает принципы функционирования баз данных и многих предметных областей. Предметные области оставим в покое, а вот принципы функционирования обсудим.
Итак, почему
SELECT
*
FROM
[categories]
WHERE
[parent] MOD @id = 0
это существенно хуже, чем
SELECT
*
FROM
[categories]
WHERE
[id] BETWEEN @low AND @high
?
Ответ прост — индексы. Первый запрос перелопачивает данные всей таблицы. Даже index scan не получается, потому что индексов способных проверить делимость не бывает. Получается table scan. Второй запрос приводит к эффективному index seek. Эффективному, так как этот seek является неизбыточным фильтром и дополнительных проверок не требуется.
Говоря проще, в первом случае для поиска детей нужно время порядка общего количества элементов, а во втором случае — порядка количества детей. Для случайного дерева асимптота скорости первого варианта — O(n), второго — O(log(n)).
Решение интересное, но не учитывает принципы функционирования баз данных и многих предметных областей. Предметные области оставим в покое, а вот принципы функционирования обсудим.
Итак, почему
SELECT
*
FROM
[categories]
WHERE
[parent] MOD @id = 0
это существенно хуже, чем
SELECT
*
FROM
[categories]
WHERE
[id] BETWEEN @low AND @high
?
Ответ прост — индексы. Первый запрос перелопачивает данные всей таблицы. Даже index scan не получается, потому что индексов способных проверить делимость не бывает. Получается table scan. Второй запрос приводит к эффективному index seek. Эффективному, так как этот seek является неизбыточным фильтром и дополнительных проверок не требуется.
Говоря проще, в первом случае для поиска детей нужно время порядка общего количества элементов, а во втором случае — порядка количества детей. Для случайного дерева асимптота скорости первого варианта — O(n), второго — O(log(n)).
Не знаю как в MySQL (давно плотно не занимался), но в PostgreSQL этот велосипед давным давно изобретен и называется ltee. В сочетании с GIN индексом — идеальное решение.
Неужели нельзя было всё это написать в 5 раз короче, пока до сути дойдёшь, можно уснуть…
Идея, на мой взгляд, бредовая по нескольким причинам:
1. Невозможно использование внешних ключей.
2. Если узел будет удалён, то нужно пересчитывать parent у всех узлов, которые в узле находятся.
3. Непонятно как генерировать id для узлов, автоинкремент тут не сработает.
Есть проверенный способ: определить рекурсивную функцию isParent запросы с ней достаточно просто пишутся. В добавок её можно и на ограничение повесить, чтобы новые узлы не зацикливали дерево.
Идея, на мой взгляд, бредовая по нескольким причинам:
1. Невозможно использование внешних ключей.
2. Если узел будет удалён, то нужно пересчитывать parent у всех узлов, которые в узле находятся.
3. Непонятно как генерировать id для узлов, автоинкремент тут не сработает.
Есть проверенный способ: определить рекурсивную функцию isParent запросы с ней достаточно просто пишутся. В добавок её можно и на ограничение повесить, чтобы новые узлы не зацикливали дерево.
Хотя, я соглашусь, в методе есть здравая мысль. Но к БД её не стоит применять.
Можно было короче. Я старался придерживаться определенного порядка изложения.
1. Почему это?
2. Это к любым методам
3. Как вариант — брать очередной id из заготовленной таблицы простых чисел. Хотя да, это самое узкое место.
Можно. Так все и делают. Мне было интересно, можно ли этого избежать.
1. Почему это?
2. Это к любым методам
3. Как вариант — брать очередной id из заготовленной таблицы простых чисел. Хотя да, это самое узкое место.
Можно. Так все и делают. Мне было интересно, можно ли этого избежать.
Идея выглядит соблазнительной на первый взгляд, но при попытке реализации вылазят разные нюансы. Мы пытались нечто подобное внедрять примерно лет 10 назад. Подробностей я уже, к сожалению, не помню, но в общих чертах идея провалилась из-за: a) проблем с масштабированием при большом кол-ве элементов; b) математические расчёты, необходимые при использовании этого подхода, работали далеко не так быстро, как интуитивно ожидалось; c) было найдено более простое и эффективное решение.
Безусловно, во вселенной должны существовать задачи, для которых этот подход окажется самым простым, эффективным и элегантным. Но я бы Вам рекомендовал проверить его на практике, на конкретной задаче, сравнить с альтернативной (например, более традиционной) реализацией, и уже по результатам писать статью.
Безусловно, во вселенной должны существовать задачи, для которых этот подход окажется самым простым, эффективным и элегантным. Но я бы Вам рекомендовал проверить его на практике, на конкретной задаче, сравнить с альтернативной (например, более традиционной) реализацией, и уже по результатам писать статью.
А что же нам предлагают сами разработчики мускула? Ах… банальщина — Nested Set или вложенные множества?
UFO just landed and posted this here
Как насчет переноса узла от одного родителя к другому?
Как и везде — обновляем поле «родитель». В случаях, когда хранятся полные пути — все гораздо сложнее.
Смена PK у части узлов?
Пример необходимости так делать? К слову, подумал еще сегодня и понял, что лучше не ПК делать простым числом, а какое-нибудь дополнительное поле. Сразу снимается масса вопросов при инсерте.
За такие вещи руки надо рвать по самые гланды.
Очень конструктивно.
Как и везде — обновляем поле «родитель». В случаях, когда хранятся полные пути — все гораздо сложнее.
Смена PK у части узлов?
Пример необходимости так делать? К слову, подумал еще сегодня и понял, что лучше не ПК делать простым числом, а какое-нибудь дополнительное поле. Сразу снимается масса вопросов при инсерте.
За такие вещи руки надо рвать по самые гланды.
Очень конструктивно.
UFO just landed and posted this here
Для реализации на реаляционных БД такой подход не приемлем, слишком медленно.
Но, всё равно, спасибо за статью. Тут есть о чём подумать. К примеру, так можно хранить не только деревья, но и графы (даже направленные). Факторизация для компьютеров которые мы используем чудовищно сложная задача, но, почему-то мне кажется что должен существовать альтернативный вариант, для которого язык простых чисел — естественный
Но, всё равно, спасибо за статью. Тут есть о чём подумать. К примеру, так можно хранить не только деревья, но и графы (даже направленные). Факторизация для компьютеров которые мы используем чудовищно сложная задача, но, почему-то мне кажется что должен существовать альтернативный вариант, для которого язык простых чисел — естественный
Намекните, пожалуйста, что вы имеете в виду?
Я имел в виду что будет медленно работать mod на любых существующих БД. На Хабре используются Nested Sets, изначально были плохо реализованные материализованные пути, но я видел и более качественную их реализацию. Потянет ли их Хабр, мно точно не известно, сейчас я думаю что, может быть, да.
По поводу компьютеров работающих с натуральными числами — это только домыслы. Просто мне кажется, что такое возможно.
По поводу компьютеров работающих с натуральными числами — это только домыслы. Просто мне кажется, что такое возможно.
А, понял, я этот способ и имел в виду под «хранением полного пути». Мне более симпатичен вариант, когда имеется отдельная таблица, где просто идет полное перечисление всех родителей для каждого узла. Так более громоздко, но зато запросы строятся только средствами SQL, без всяких вычислений и разбиений строк.
UFO just landed and posted this here
Sign up to leave a comment.
Иерархия в БД на простых числах