Здравствуйте, многоуважаемые.
Задача довольно избитая — хранить дерево в реляционной БД. Само по себе не сложно, но некоторые практические вопросы заставляют сильно наморщить мозг. Есть много интересных решений, но вот пришло мне в голову еще одно. Не уверен, что оно оригинальное, но такого решения я не встречал.
Придумать способ хранения дерева в БД — не сложно. Сложно придумать так, чтобы данные легко было доставать. Вот несколько самых типичных задая:
Первые два пункта в описываемом решении выполняются очень простым запросом, без всяких объединений и подзапросов, независимо от глубины иерархии.. По последнему пункту — еще не успел продумать :(
Я исхожу из не самой типичной структуры данных, а потому хочу ее слегка пояснить. Имеется таблица сущностей (полностью зависит от предметной области, пусть будет, допустим, список товаров). В каждой строке добавляем еще одно поле — идентификатор категории товаров. А вот сами категории находятся в другой таблице. Эта ситуация немного отличается от довольно распространенной схемы, где имеется одна таблица, описывающая все сущности, а для каждой сущности вводится поле, уточняющее, является ли эта сущность узлом, имеющим потомки, или бездетным узлом (листом дерева).
Иными словами, листья — в одной таблице, все узлы — в другой таблице.
Типично для того, чтобы описать иерархию узлов, в таблицу дополнительно вводится поле parent, в которое записывается идентификатор родительского узла, либо NULL, если узел является корнем (а то и вовсе корень только подразумевается, а для «первых побегов» корня указывается parent=NULL).
Если пренебречь порядком следования узлов на одном уровне (все «братские» узлы), как это допускает большинство задач, то вышеописанной структуры достаточно для исчерпывающего (в рамках задачи) описания структуры. Это предположение сделано для простоты, для учета порядка следования братьев таблицу узлов потребуется малозначительно дополнить, и эти дополнения каждый может сочинить без труда.
Проблемы, однако, начинаются, когда требуется провернуть чего-нибудь этакого, например, отобразить все подузлы текущего узла на сколько-то уровней потомства. Для этого приходится несколько раз обращаться к таблице структуры (узлов), выбирая каждый раз нужный узел по заданной иерархии. К примеру, возвращается набор идентификаторов первых потомков, затем для каждого полученного идентификаторы повторяем операцию и т.д. до нужной глубины иерархии.
Иными словами, приходится использовать рекурсивные функции. Чтобы избежать такого некрасивого и ресурсоемкого решения, придумывают различные дополнительные таблицы, в которых бы хранилась эта вспомогательная информация. Довольно хорошее решение, но, простите, громоздкое. Хотелось бы чего-нибудь изящного, простого, и чтобы запросы выглядели очень понятными.
Несколько решений существует, навскидку упомню парочку:
Сразу оговорюсь, что, возможно (даже скорее всего) оно не именно мое и кем-то придумано и используется, но я ниоткуда не копипастил и не списывал, а потому позволю себе назвать это решение «моим» :)
Так вот, мое решение является разновидностью второго типа решений, но лишено многих недостатков большинства имеющихся реализаций. Имеет, правда, и свои собственные ;) Но по здравому рассуждению, не ощутимые для иерархи с числом узлов, думается, порядка нескольких сотен тысяч. Но об этом чуть ниже.
В таблице узлов в качестве идентификаторов использовать простые числа, а в поле «parent» — произведение идентификаторов всех предков.
Изящное построение некоторых запросов, т.к. можно за одно действие точно выяснить, находятся ли определенные два узла в отношения «родитель» — «потомок».
Как известно, каждое сложное число однозначно раскладывается на простые множители. Следовательно, признаком имеющихся родственных связей родитель-потомок (независимо от расстояния по иерархии) будет являться делимость поля «parent» предполагаемого потомка на идентификатор предполагаемого родителя. Или, чуть меняя формулировку, выражение
Талица категорий (узлов) имеет самую простую структуру:
Выбор всех узлов, имеющих заданный среди предков:
Чтобы вычислить поле parent для нового узла, надо всего лишь перемножить поля id и parent новоиспеченного родителя.
По поводу первого пункта — тут прошу помощи у хабралюдей :) В качестве основной задачи предлагаю прикинуть различные запросы, требуемые для работы с каталогом товаров.
По второму пункту хочу немного пояснить. Во-первых, по поводу количества простых чисел: в диапазоне от 1 до одного миллиарда находится порядка 50 миллионов простых чисел. Иными словами, в 10 разрядов (по умолчанию в MySQL используются 11 разрядов для INT) можно впихнуть 50 миллионов узлов. Правда, с полем «parent» ситуация более грустная: если у нас 50 миллионов узлов, то размера INT(11) нам может не хватить :(… Хватит или нет — зависит от вида конкретной структуры.
Генерировать простые числа — задача неблагодарная, но для каталога товаров (а там групп/подгрупп обычно не больше нескольких сотен) — вполне решаемая.
Если немного выйти за рамки каталога товаров, то для получения нового простого числа (идентификатора нового узла) можно использовать таблицу простых чисел. Т.е. прямо в БД завести таблицу простых чисел, одно поле — порядковый номер, второе — соответственное простое число. Заранее прикинув мощность иерархии, можно создать таблицу простых чисел подходящего размера.
Однако, насколько я могу судить, изменение иерархии категорий происходит гораздо реже извлечения данных об иерархии.
Задача довольно избитая — хранить дерево в реляционной БД. Само по себе не сложно, но некоторые практические вопросы заставляют сильно наморщить мозг. Есть много интересных решений, но вот пришло мне в голову еще одно. Не уверен, что оно оригинальное, но такого решения я не встречал.
Придумать способ хранения дерева в БД — не сложно. Сложно придумать так, чтобы данные легко было доставать. Вот несколько самых типичных задая:
- Проверить, является ли данный узел потомком заданного узла
- Выбрать все узлы-потомки данного узла
- Выбрать всех предков заданного узла
Первые два пункта в описываемом решении выполняются очень простым запросом, без всяких объединений и подзапросов, независимо от глубины иерархии.. По последнему пункту — еще не успел продумать :(
Структура данных
Я исхожу из не самой типичной структуры данных, а потому хочу ее слегка пояснить. Имеется таблица сущностей (полностью зависит от предметной области, пусть будет, допустим, список товаров). В каждой строке добавляем еще одно поле — идентификатор категории товаров. А вот сами категории находятся в другой таблице. Эта ситуация немного отличается от довольно распространенной схемы, где имеется одна таблица, описывающая все сущности, а для каждой сущности вводится поле, уточняющее, является ли эта сущность узлом, имеющим потомки, или бездетным узлом (листом дерева).
Иными словами, листья — в одной таблице, все узлы — в другой таблице.
Типично для того, чтобы описать иерархию узлов, в таблицу дополнительно вводится поле parent, в которое записывается идентификатор родительского узла, либо NULL, если узел является корнем (а то и вовсе корень только подразумевается, а для «первых побегов» корня указывается parent=NULL).
Суть задачи
Если пренебречь порядком следования узлов на одном уровне (все «братские» узлы), как это допускает большинство задач, то вышеописанной структуры достаточно для исчерпывающего (в рамках задачи) описания структуры. Это предположение сделано для простоты, для учета порядка следования братьев таблицу узлов потребуется малозначительно дополнить, и эти дополнения каждый может сочинить без труда.
Проблемы, однако, начинаются, когда требуется провернуть чего-нибудь этакого, например, отобразить все подузлы текущего узла на сколько-то уровней потомства. Для этого приходится несколько раз обращаться к таблице структуры (узлов), выбирая каждый раз нужный узел по заданной иерархии. К примеру, возвращается набор идентификаторов первых потомков, затем для каждого полученного идентификаторы повторяем операцию и т.д. до нужной глубины иерархии.
Иными словами, приходится использовать рекурсивные функции. Чтобы избежать такого некрасивого и ресурсоемкого решения, придумывают различные дополнительные таблицы, в которых бы хранилась эта вспомогательная информация. Довольно хорошее решение, но, простите, громоздкое. Хотелось бы чего-нибудь изящного, простого, и чтобы запросы выглядели очень понятными.
Несколько решений существует, навскидку упомню парочку:
- Нумерация всех узлов в определенном порядке обхода.
К сожалению, утратил ссылку на первоисточник.Спасибо adontz за ссылку. Позволяет делать очень простые и наглядные select'ы, но есть один недостаток: требуется пренумеровывать узлы при любом изменении иерархии (например, создание новой категории товаров) - Хранение полного пути до текущего узла. Ресурсоемко и не очень удобно. Как вариант — путь «кодируется» в виде числа, в котором каждый разряд указывает на идентификатор конкретного предка. Например, число «53» могло бы обозначать, что текущий узел находится в пятой подгруппе третьей группы. Очевидный недостаток такого представления — жесткие ограничения на количество групп/подгрупп
Мое решение
Сразу оговорюсь, что, возможно (даже скорее всего) оно не именно мое и кем-то придумано и используется, но я ниоткуда не копипастил и не списывал, а потому позволю себе назвать это решение «моим» :)
Так вот, мое решение является разновидностью второго типа решений, но лишено многих недостатков большинства имеющихся реализаций. Имеет, правда, и свои собственные ;) Но по здравому рассуждению, не ощутимые для иерархи с числом узлов, думается, порядка нескольких сотен тысяч. Но об этом чуть ниже.
Предлагаю:
В таблице узлов в качестве идентификаторов использовать простые числа, а в поле «parent» — произведение идентификаторов всех предков.
Что это дает?
Изящное построение некоторых запросов, т.к. можно за одно действие точно выяснить, находятся ли определенные два узла в отношения «родитель» — «потомок».
Как известно, каждое сложное число однозначно раскладывается на простые множители. Следовательно, признаком имеющихся родственных связей родитель-потомок (независимо от расстояния по иерархии) будет являться делимость поля «parent» предполагаемого потомка на идентификатор предполагаемого родителя. Или, чуть меняя формулировку, выражение
parent MOD <идентификатор родителя> = 0Пара примеров
Талица категорий (узлов) имеет самую простую структуру:
CREATE TABLE categories (`id` INT(11), `parent` INT(11), `name` VARCHAR(50), PRIMARY KEY `id`);Выбор всех узлов, имеющих заданный среди предков:
SELECT * FROM `categories`
WHERE `parent` MOD <`id` заданного узла> = 0;Чтобы вычислить поле parent для нового узла, надо всего лишь перемножить поля id и parent новоиспеченного родителя.
Недостатки
- Не все еще продумал ;)
- Простые числа — страшные звери, на них непросто охотиться...
- Дополнительно накладывается ограничение на сложность иерархии в том смысле, что каждое поле parent — это перемножение идентификаторов всех родителей, а для развитой иерархии потребуется довольно большой размер поля (правда, решается использованием BIGINT )
- Неудобен поиск всех предков: приходится производить факторизацию поля parent
По поводу первого пункта — тут прошу помощи у хабралюдей :) В качестве основной задачи предлагаю прикинуть различные запросы, требуемые для работы с каталогом товаров.
По второму пункту хочу немного пояснить. Во-первых, по поводу количества простых чисел: в диапазоне от 1 до одного миллиарда находится порядка 50 миллионов простых чисел. Иными словами, в 10 разрядов (по умолчанию в MySQL используются 11 разрядов для INT) можно впихнуть 50 миллионов узлов. Правда, с полем «parent» ситуация более грустная: если у нас 50 миллионов узлов, то размера INT(11) нам может не хватить :(… Хватит или нет — зависит от вида конкретной структуры.
Генерировать простые числа — задача неблагодарная, но для каталога товаров (а там групп/подгрупп обычно не больше нескольких сотен) — вполне решаемая.
Если немного выйти за рамки каталога товаров, то для получения нового простого числа (идентификатора нового узла) можно использовать таблицу простых чисел. Т.е. прямо в БД завести таблицу простых чисел, одно поле — порядковый номер, второе — соответственное простое число. Заранее прикинув мощность иерархии, можно создать таблицу простых чисел подходящего размера.
Однако, насколько я могу судить, изменение иерархии категорий происходит гораздо реже извлечения данных об иерархии.