Комментарии 25
@MericaDotNet,
Сейчас в новостях Хабра ваша статья размещена полностью и раздражает излишним размером.
Пока вам не опустили рейтинг ниже плинтуса, разделите пож. вашу статью, чтоб над катом была малая часть, дающая представление о содержании, а под катом полная статья.
Очень интересно!
Nested Sets
…
левый индекс меньше 2 И правый индекс больше 11 …
левый индекс меньше или равен 2 И правый индекс больше или равен 11
Должно быть наоборот:
левый индекс > 2 И правый индекс < 11
левый индекс ≥ 2 И правый индекс ≤ 11
Materialized Path на самом деле существует в двух вариантах. Первый описан - храним имя и путь. Второй же даже не упомянут. Храним только имя, но в виде полного характеристического, т.е. с полным путём от корня. Достоинства и недостатки те же.
И ещё. Вы упустили один недостаток (хотя это, возможно, и выходит за рамки статьи). А именно трудность выявления ошибок - точнее, факта наличия циклов для Adjacency List и невалидных путей (ссылка на несуществующий узел) для Materialized Path. И если вторая проблема при правильной работе с данными может быть только последствием какого-то сбоя, который сам по себе есть основание для валидации, то вот факт образования цикла при штатном изменении данных никак себя не проявляет. Для остальных методов хранения выявление ошибок проще (вернее, выше вероятность выявления факта наличия ошибки и необходимости валидации и санации при очередной операции с данными), особенно если узел хранит уровень.
Могу лишь добавить, что если данных в основной таблице с деревом не очень много, а возиться с обновлением «Closure Table» не охота, то в принципе, можно обойтись и «view» c рекурсивной CTE, позже заменив её на реальную таблицу (в случае проблем с производительностью).
;WITH CTE_Recursive AS (
SELECT
Id,
ParentId
FROM dbo.TreeData
UNION ALL
SELECT
[PREVIOUS].Id,
[CURRENT].ParentId
FROM dbo.TreeData
[CURRENT]
INNER JOIN CTE_Recursive
[PREVIOUS] ON
[PREVIOUS].ParentId = [CURRENT].Id
)
,CTE_TreeRelation AS
(
SELECT
Id,
ParentId
FROM CTE_Recursive
UNION ALL
SELECT
Id, Id as ParentId
FROM dbo.TreeData
)
SELECT * FROM CTE_TreeRelation
Конкретно я использовал древовидное хранение в складском хозяйстве. На складе используется адресное хранение, ну а ячейки, разумеется, имеют иерархическую структуру: "Зона склада" -> Стеллаж -> Полка -> Ячейка.
Ну и вишенкой на торте является маркировка товаров: все упаковки и коробки пронумерованы, а в БД хранится информация об их вложенности. Это используется для своеобразной отчётности в государственном мониторинге лекарственных препаратов.
Это было бы интересно почитать в виде отдельной статьи?
В моем случае масса деревьев (MSSQL).
Нужно простое решение по созданию, заполнению и начитке.
Последние 15+ лет использую Adjacency List.
Лет 10 назад перешел с рекурсивного CTE на динамически создаваемый запрос через SQL CLR с возможность фильтровать и сортировать отдельно по корневой в вложенной ветке.
Полет нормальный, проблем с производительсностью нет, а структура дерева максимально простая.
Используем Adjacency List для хранения дерева файловой системы (порадка 10^9 файлов) . Плюс: быстрый листинг директории и перемещение файлов. Минус: нужна рекурсия чтобы достать ветку дерева.
Вариант с Closure Table создаёт неоправданно много записей для сильмп вложенных путей.
Я пришел к выводу что лучше всего комбинировать AL+MP, это даёт лёгкое получение всех основных операций, а из недостатков - только сложности с обновлением детей родителя при его перемещении, что обычно не очень частая операция, которая к тому же легко выполняется за счёт индекса.
NS - вообще годится только для маленьких деревьев, так как вставка в начало большого дерева - это дикая боль, пересчитывающее все дерево.
Это как так? Обычно операций чтения из базы в тысячи и миллионы раз больше, чем записи. А выборка из AL куска большого дерева - это десятки рекурсивных операций выборки. Да оно будет умирать на больших деревьях. Как раз NS позволяет крайне быстро одной операцией произвести выборку. Да, изменить дерево дольше, но это случается крайне редко по сравнению с чтением. Да и не так уж это сложно.
Materialized Path даёт возможность сделать выборку легко в этом случае: `select * from tree where path like 'branch2/%'`. Как и писал комбинация AL+MP даёт, имхо, самую лучший вариант для любого дерева. А NS умирает если вставить в начало дерева из >10000 элементов.
MP всё же довольно специфичен. Например, многие базы не умеют использовать индекс при поиске в тексте с "%" (особенно, если он в начале). А тогда вообще караул. К тому же потом надо будет разбирать отдельно (на стороне SQL или в приложении) эту строку, чтобы получить именно связи между элементами, а не текстовые пути. Т. е. если есть элемент, чью ветку на 3 уровня вверх и на 3 уровня вниз, нам надо получить, то нам нужно найти этот элемент в базе, получить его строку с путём, разложить эту строку на компоненты, составить запрос (а возможно и несколько - как минимум 2, сверху и снизу элемента), получить от запроса эти элементы, снова у каждого элемента разобрать путь и уже тогда проставить ссылки. Так что тут тоже заморочек много. Не говоря уже о том, чтобы соединить это с AL.
Обычно, если надо вставить 10000 элементов, то их сначала готовят (проставляют индексы), а потом вставляют batch-ем. Так то да, если обновлять дерево после каждого то будет долго. Но опять же, только в начале. Потом очень высокая скорость работы всё компенсирует.
Это что за БД такая, которая не умеет юзать индексы на like с процентом в конце?
По скорости замеры проводил тут.
Полезность nested sets имхо преувеличена.
Да вот бывают такие. А с процентом в начале вообще всё плохо. Кстати, лучше MP делать не в виде строки, а в виде массива. И сериализовать его в поле в типе json/xml. В наше время БД скорее сможет индексировать json (и иметь специальный синтаксис по работе с полями/индексами такой сущности), чем нормально строку.
Тут есть ещё одно обстоятельство. Собственно самой программе при работе с деревом в виде объектов практически всегда удобнее именно иметь в некоем виде AL - т. е. чтобы объект имел ссылку на родителя и/или коллекцию ссылок на потомков. Что приводит нас к тому, что AL можно просто получить через ORM и начать пользоваться, а MP/NS придётся ещё дополнительно конвертировать.
Так что выбор очень сложный. И очень сильно зависит от конкретных условий.
P. S. Ещё забыл упомянуть, что индекс на строки, позволяющий полнотекстовый поиск (ну или на json с работой с его полями) - штука сама по себе довольно сложная и капризная. И тут накладные расходы тоже могут очень большие, особенно если DBA не озаботился кодовой страницей для этой строки и индекс вынужден будет (даже если их на самом деле в строке в принципе не будет) учитывать всякие умляуты, большие/маленькие буквы и прочие особые кодовые пары из юникода.
В начале процент и не нужен для MP. MySQL/PG/SQL Server/SQLite - 100% норм индексируют like с процентом на конце, у вас видимо экзотика. А вот в json или массивах точно не стоит это хранить, по крайней мере если хочется нормальный индекс) В лучшем случае это хранить в специализированных типах, типа ltree в pg.
Полнотекстовый поиск тут точно не нужен. Тут вообще можно collate на binary включить.
MP по сравнению с NS - очень легко готовится:
1) чтобы добавить элемент - берём path родителя, и добавляем к нему идентификатор элемента, таким образом получая новый path
2) Чтобы переместить узел просто меняем подстроку пути у всех элементов по like 'path%'
Для деревьев использовали внешнюю таблицу на основе AL+MP + добавляли childIndex для сортировки детей. Если нужно было объединять в иерархию несколько сущностей (таблиц), то вместо одной ссылки на таблицу сущностей добавлялось больше столбцов-ссылок. Непротиворечивость ссылок в рамках одной записи обеспечивалось дополнительным столбцом с индексом сущности.
Создание иерархии во внешней таблице позволяет избежать модификации основный таблиц и строить больше одной иерархии на основе базовой таблицы. Недостатком такого подхода является необходимость поддерживать актуальность иерархических таблиц вместе с основными.
А почему в качестве критериев выбраны только сложность вставки и получения дочерних элементов. Неужели больше никаких операций с деревьями производит не приходится? Ну там получить полный путь, например. Еще что с деревьями, где может быть несколько родителей у одного узла?
Путь можно хранить как строку, кодируя в каждом ее символе номер дочернего элемента в родителе. Например "0213". Все дочерние элементы это элементы у которых путь начинается с пути родителя. Порядок элемента - это длина строки. В случае бинарного дерева путь можно хранит как длинное число - последовательность нулей и единиц. Поиск детей будет сравнением по бинарной маске родителя, порядок - округленным вверх логарифмом по основанию 2. Правда возникнкт ограничение на глубину дерева..
При использовании целочисленных типов для левого и правого индекса и уровня необходимо пересчитывать индексы всех связанных элементов
Вопрос по Nested sets.
А какого типа должны быть индексы чтобы их не приходилось пересчитывать?
Обзор паттернов хранения деревьев в реляционных БД