Дерево в реляционной базе данных

Автор(ы): Чобиток Василий 14:21, 11 июля 2007 (EEST)

G+ В компьютерных программах часто используется древовидное представление данных (например, в древовидном представлении очень удобно просматривать ход обсуждения какой-либо темы в процессе переписки или на форуме).

Как правило, хранение данных, имеющих древовидную структуру, организовывается в реляционной СУБД с использованием двух ключевых полей — первичного уникального ключа (обозначим его ID) и вторичного (PID), ссылающегося на ID ближайшего узла верхнего уровня (родителя). Если текущий узел корневой, в зависимости от реализации PID может быть равен −1, 0 или null.

Если дерево небольшое, хранится в отдельной таблице и используется целиком (как правило такой вариант используется в вертикальном меню некоторых программ), то связка ID-PID прекрасно работает. Если же объём данных составляет десятки и сотни тысяч записей, а выбирать необходимо только какую-то часть дерева, тогда возникают проблемы с производительностью — для выборки дерева из БД по связке ID-PID необходимо рекурсивно выполнить большое число SQL-запросов, что сильно нагружает сервер, или одним запросом выбрать все дерево и на сервере или клиенте программно отсечь лишние данные и построить дерево, что тоже очень затратно с точки зрения нагрузки на сервер.

Рассмотрим возможный вариант решения проблемы.

Допустим, что в нашем случае для корневых узлов PID = −1.

Дополнительно вводим:

• индексированное поле rootID, которое ссылается на корневое сообщение ветки;
• и текстовое уникальное индексированное поле path.

Следует заметить, что некоторые СУБД позволяют заводить текстовое поля практически без ограничения длины с возможностью их индексации, как это принято для строковых полей ограниченной длины. Если у нас такая СУБД, то path следует проиндексировать.

Итак, поле path. В нем через точку вписаны ID всех узлов, начиная с root, для которых он является вложенным, включая ID самого узла, например так: «2.34.456.» (с точкой в конце).

Два дополнительных поля дают широкие возможности манипуляции данными с использованием простых запросов. Правда, на стороне клиента надо сделать несколько вариантов обработки, но производительность при этом нас не озадачивает.

Если SQL-запросом необходимо выбрать ветку для заданного корня ID=5, то это делается так:

select * from tableName
where rootID = 5

В этом случае выстроить дерево на клиенте — дело техники (по связке ID, PID или по path), при этом сервер не нагружен.

Если нужно выбрать дерево для десяти корневых сообщений — выборка с PID = −1 и LIMIT 10, по каждому дополнительный запрос как в предыдущем варианте. То есть число запросов получается не по количеству сообщений в дереве, а по числу корневых сообщений + 1.

Самое хитрое — выборка части дерева не с корня, например для узла «5.12.33».

Можно просто выбирать:

select * from tableName
where path like '5.12.33.%'

(обратите внимание на точку, добавленную к коду перед знаком процента, без нее могут быть выбраны и записи с кодом «5.12.333», не имеющие отношения к нашей ветке)

поскольку поле проиндексировано, то для начала строки индекс отработает. Если с индексом по длинному тексту проблема, возможен такой вариант:

select * from tableName
where rootID = 5 and path like '5.12.33.%'

При правильном оптимизаторе отработает выборка по проиндексированному root, после чего уже по ограниченному набору данных будет происходить LIKE.