Комментарии 27
Позновательно! +
Было бы интересно провести тест при параболическом распределении узлов. т.е. вначале детей немного, потом количество резко увеличивается, а потом падает. IMHO, такое распределение больше приближено к жизни. Впрочем, полагаю, реально картина если и изменится, то не сильно.
А еще есть пара полезных операций — как то смена порядка следования детей внутри родительского узла (и лучше смена на произвольное количество позиций), а также копирование ветки (то есть добавление в середину дерева не узла, но ветви произвольного размера).
P.S. алгоритмы AL можно серьезно оптимизировать, добавив level и havechild (тот же самый уровень и признак наличия потомков) Происходит некоторое замедление добавления (принудительный апдейт или апдейт с проверкой), удаления и апдейта (на отдельных операциях — ровно на проверку а остались ли еще дети).
А еще есть пара полезных операций — как то смена порядка следования детей внутри родительского узла (и лучше смена на произвольное количество позиций), а также копирование ветки (то есть добавление в середину дерева не узла, но ветви произвольного размера).
P.S. алгоритмы AL можно серьезно оптимизировать, добавив level и havechild (тот же самый уровень и признак наличия потомков) Происходит некоторое замедление добавления (принудительный апдейт или апдейт с проверкой), удаления и апдейта (на отдельных операциях — ровно на проверку а остались ли еще дети).
На самом деле закон распределения не имеет такого сильного значения. Нас ведь в любом случае будет интересовать производительность в точке, в которой сосредоточено максимальное кол-во узлов, поэтому просто важно знать какой он. Есть две крайности — равномерное распределение и распределение с явным большим перекосом. При этом заведомо понятно, что при равномерном мы получим стабильное но не самое высокое время отработки. А в случае с перекосом мы увидим пик нагрузки. А где будет этот перекос — в начале, середине или в конце дерева не столь суть важно, если он существенный.
Эхх… вот прям недавно задолбался, искал полную и подходящую инфу по этой теме, в итоге сделал не очень рационально. Чуть бы раньше эту статью
Воппрос на тему используемых баз данных — не пробовали ли вы протестировать эти алгоритмы на других базах данных? Я думаю что производительность будет очень сильно разниться.
Думаю, что будет. Но — нет — не пробовал, к сожалению.
К чему я спрашиваю. У нашей команды есть спецефическая задача — поиск по объектным структурам в базах данных. Мы там храним объекты. После исследований на эту тематику оказалось что постгресс позволяет благодаря своим разнообразным типам данных в число которых входят хэши, ускорить этот поиск в 5-10 раз.
Плюс вложеннные запросы в нем обрабатываются гораздо лучше — при поиске в базе из 100000+ элементов 3-уровневая связанность обрабатывается около 70мс. 9-уровневая связанность же окло 90мс.
в
Вобщем рекомендую попробовать.
Плюс вложеннные запросы в нем обрабатываются гораздо лучше — при поиске в базе из 100000+ элементов 3-уровневая связанность обрабатывается около 70мс. 9-уровневая связанность же окло 90мс.
в
Вобщем рекомендую попробовать.
статья супер, побольше-бы такого материала на хабре. Автору спасибо, ждем продолжения
в избранное, сразу же.
спасибо
спасибо
Прошлую статью прочитал мельком. Увидев эту, сел перечитывать прошлую еще раз, дабы все по полочкам разложить.
Спасибо за громадный труд.
Спасибо за громадный труд.
Работа серьезная, но хотелось бы отметить что в реальной практике редко бывает такое, чтобы необходимо было выбрать что-то одно из представленных типов структур.
По собственному опыту говорю, что зачастую изначально строиться AL, затем туда добавляются Path из MP и возможно что-то из NS. Причем основные операции проходят через AL структуру, а специфичные задачи используют, то что нарастили из других структур.
По собственному опыту говорю, что зачастую изначально строиться AL, затем туда добавляются Path из MP и возможно что-то из NS. Причем основные операции проходят через AL структуру, а специфичные задачи используют, то что нарастили из других структур.
Спасибо за проделанную работу. Маленькое замечание: в легенде к графикам слишком узкие полоски, поэтому цвет непонятен, и сделайте цвета поконтрастнее относительно друг друга.
Спасибо за исследование, мальком просмотрел — вникну позже.
Сам на маленьких деревьях (до 1000 узлов) тупо гружу их в память и уже там разбираюсь что к чему… в приложениях FastCGI + кэширование, думаю, ни один SQL-подход не сделает быстрее.
Сам на маленьких деревьях (до 1000 узлов) тупо гружу их в память и уже там разбираюсь что к чему… в приложениях FastCGI + кэширование, думаю, ни один SQL-подход не сделает быстрее.
Жаль, что не было сравнения соструктурой, где путь формируется второй таблицей (nodeAndItsAncestors).
При вставке узла в эту таблицу вставляем
insert into nodeAndItsAncestors(id, parentId) values(@id, @id);
insert into nodeAndItsAncestors(id, parentId) select @id, parentId from nodeAndItsAncestors where id = @parentId;
Все выборки по дереву легко выполняются именно по этой таблице.
При вставке узла в эту таблицу вставляем
insert into nodeAndItsAncestors(id, parentId) values(@id, @id);
insert into nodeAndItsAncestors(id, parentId) select @id, parentId from nodeAndItsAncestors where id = @parentId;
Все выборки по дереву легко выполняются именно по этой таблице.
Что хочется сразу сказать.
Реализации алгоритма MP — ужасающа. Поэтому и результаты такие.
Какая может быть «скорость», при все время «вычисляемых» результатах ;)
Ну нельзя пользоваться в mysql строчными функциями при «вычислениях» полей.
Кстати MP самый малоизученный алгоритм, поэтому и получилось «такое».
Поэтому результаты не считаю правильными и обьективными, так условия теста получаются не равные ;)
Реализации алгоритма MP — ужасающа. Поэтому и результаты такие.
Какая может быть «скорость», при все время «вычисляемых» результатах ;)
Ну нельзя пользоваться в mysql строчными функциями при «вычислениях» полей.
Кстати MP самый малоизученный алгоритм, поэтому и получилось «такое».
Поэтому результаты не считаю правильными и обьективными, так условия теста получаются не равные ;)
Автор, ты просто молодец. Я отослал ссылку на пост всем заинтересованным друзьям и сам добавил в избранное. Большое тебе хабраСпасибо (уж прости, что просто «спасибо»)
Я что-то не пойму, неужели Adjacency List быстрее всех в разы? ради чего тогда создавались алгоритмы NS и MP?? Только чтоб избавится от лишних джойнов в запросах?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Иерархические структуры данных и производительность