Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 26
Я нашел элегантный способ как решить эту проблему всего лишь чуть-чуть изменив стандартный Nested Set. Идея его проста [...] Ко всем нодам следует добавить идентификатор поддерева в котором они находятся, например id корня.Из ваших слов складывается впечатление, что вы первый, кто нашёл это способ…
Больше нигде в интернете его не встречал и не знаю ни одной библиотеки которая бы использовала такой подход
Tree из DoctrineExtensions, например.
С того что я вижу, они сохраняют значение root но не делают отдельный отсчет left и right в поддеревьях. При вставке все равно приходится сдвигать все элементы правее от новой ноды. То есть для оптимизации оно не используется и несет разве что удобство при написании запросов:
//получить все дети поддерева 1
$query = $entityManager
->createQueryBuilder()
->select('node')
->from('Entity\Category', 'node')
->where('node.root = 1')
->getQuery();
Scope из Baum (реализация Nested Set для Laravel)
Тяжеловато как-то выглядит.
Лет пять назад я для себя «изобрел» NI.
Не помню подробности, но вроде просто отказался от того что нумерация идет подряд, и у «листа» (одиночного узла без потомков) разница между левым и правым могла быть и 100000. Плюс если таки было нужно двигать, то двигал я не строго в лево, но мог и вправо если это ближе… Если не ошибаюсь понадобилось лишь добавить уровень(относительно корня), чтобы сохранить старую функциональность.
А вообще НС хорошая штука, но не всегда нужна. Нужно думать зачем. Какие операции более частые и сравнивать цену операций. Я в большинстве задач ушел на более простые модели.
Лет пять назад я для себя «изобрел» NI.
Не помню подробности, но вроде просто отказался от того что нумерация идет подряд, и у «листа» (одиночного узла без потомков) разница между левым и правым могла быть и 100000. Плюс если таки было нужно двигать, то двигал я не строго в лево, но мог и вправо если это ближе… Если не ошибаюсь понадобилось лишь добавить уровень(относительно корня), чтобы сохранить старую функциональность.
А вообще НС хорошая штука, но не всегда нужна. Нужно думать зачем. Какие операции более частые и сравнивать цену операций. Я в большинстве задач ушел на более простые модели.
> Я долго думал использовать ли этот подход или же Closure Table для хранения деревьев в SQL базах
Вообще надо понимать, что в зависимости от характера использования иерархических данных хранить их можно по-разному. Например, для дешевой операции вставки — тривиальный adjacent list, для дешевого поиска — nested set.
Вот здесь есть шикарное описание разных способов хранения деревьев в реляционных БД.
stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database
Возможно, в примере с комментариями к статьям, приведенным автором, nested set — как раз не лучший вариант. По ссылке на SO предлагают Flat Table в этом случае.
Вообще надо понимать, что в зависимости от характера использования иерархических данных хранить их можно по-разному. Например, для дешевой операции вставки — тривиальный adjacent list, для дешевого поиска — nested set.
Вот здесь есть шикарное описание разных способов хранения деревьев в реляционных БД.
stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database
Возможно, в примере с комментариями к статьям, приведенным автором, nested set — как раз не лучший вариант. По ссылке на SO предлагают Flat Table в этом случае.
На самом деле я собирался сделать оба варианта, чтобы пользователь мог сам выбрать чем пользоваться. Но так как время у меня ограниченное хотелось начать с более общего подхода.
Кстати если активных пользователей так много что вставка происходит часто, то скорее всего читателей которые не комментирует еще на порядок больше. А в последнее время я в обще склоняюсь к тому чтобы хранить комментарии в монге для удобства.
Кстати если активных пользователей так много что вставка происходит часто, то скорее всего читателей которые не комментирует еще на порядок больше. А в последнее время я в обще склоняюсь к тому чтобы хранить комментарии в монге для удобства.
А можно скрестить adjacency list и closure table. Работать будет очень быстро.
Есть еще materialized path. Тоже неплохой способ хранить деревья.
он хорош, но только для деревьев которые не особо глубоки, а то все эти опереции с префиксами на стрингах начинают сильно тормозить. Правда как бонус путь можно сразу использовать для постройки УРЛов в рутере =)
Путь можно по колонкам разбить. С такой реализацией и быстро и довольно дешево редактировать. Ограничение по глубине можно обходить используя дополнительные таблицы.
Тормоза от LIKE запросов, которые необходимы при поиске детей ноды.
LIKE «prefix%» через индекс же идет
Этот индекс все равно медленнее числовых, к тому же при поиске вверх (найти всех родителей) уже не помогает. Да и при собирании объектного дерева из таких записей приходится на каждой делать explode() а это тоже не дешево в большых количествах
Так родители то в пути уже и прописаны. На то он и МП.
Братья через префикс%, Дяди — через префикс%. В общем то любые родственники одного уровня (двоюродные дедушки, и т.п.) через префикс%. А, ну да, это работает если к МП добавить еще поле уровень.
А других поисков по предкам я на своей практике и не припомню. Описанные дяди и двоюродные дедушки у меня встречались часто в различных менюшках, когда дерево было деревом страниц на сайте.
Вообще по моему опыту который в деревьях небольшой — НС имеет лишь одно преимущество перед НИ — простота. При этом не так много задач где они оба имеют преимущества над другими. Ну в НС количество потомков можно получить без запросов в отличии от интервалов. Но…
Вообще тут нужно реальные тесты делать, а не гадать. У меня к примеру большие сомнения что в реальной задаче хоть когда-то эксплоде будет узким местом. Его тяжесть довольно условна.
Братья через префикс%, Дяди — через префикс%. В общем то любые родственники одного уровня (двоюродные дедушки, и т.п.) через префикс%. А, ну да, это работает если к МП добавить еще поле уровень.
А других поисков по предкам я на своей практике и не припомню. Описанные дяди и двоюродные дедушки у меня встречались часто в различных менюшках, когда дерево было деревом страниц на сайте.
Вообще по моему опыту который в деревьях небольшой — НС имеет лишь одно преимущество перед НИ — простота. При этом не так много задач где они оба имеют преимущества над другими. Ну в НС количество потомков можно получить без запросов в отличии от интервалов. Но…
Вообще тут нужно реальные тесты делать, а не гадать. У меня к примеру большие сомнения что в реальной задаче хоть когда-то эксплоде будет узким местом. Его тяжесть довольно условна.
Не понимаю к чему ваши вопросы. Разбивая путь по колонкам имеем целочисленные колонки под идентификаторы родителей. Нужно выбрать всех детей какого-то объекта — делаем условие равенства на соответствующую колонку. Ограничение связано с максимальным количеством колонок у таблицы.
У каждого алгоритма хранения деревьев свои ограничения:
AL — сложная выборка потомков и предков (join-ы и т. п.);
NS — годится только для маленьких деревьев, т. к. вставка в начало большого дерева займёт катастрофически много времени, кроме того выборка предков тоже не достаточно быстра;
NI — очень сложная реализация, необходимость тонкой настройки
MP — из недостатков разве что чуть более медленные операции на string полем
CT — как выше сказано — кол-во записей
В принципе проводя измерения производительности, выигрывала связка AL+MP, те методы которые медленно делались AL, выполнялись MP. У такого подхода практически нет слабых мест.
AL — сложная выборка потомков и предков (join-ы и т. п.);
NS — годится только для маленьких деревьев, т. к. вставка в начало большого дерева займёт катастрофически много времени, кроме того выборка предков тоже не достаточно быстра;
NI — очень сложная реализация, необходимость тонкой настройки
MP — из недостатков разве что чуть более медленные операции на string полем
CT — как выше сказано — кол-во записей
В принципе проводя измерения производительности, выигрывала связка AL+MP, те методы которые медленно делались AL, выполнялись MP. У такого подхода практически нет слабых мест.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Оптимизация модели Nested Set в PHPixie