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

Материал из Бронетанковой Энциклопедии — armor.kiev.ua/wiki
< Участник:ArmorAdmin
Версия от 05:47, 20 декабря 2015; LostArtilleryMan (обсуждение | вклад) (LostArtilleryMan переименовал страницу Участник:ГОВНЮК/Дерево в БД в Участник:ArmorAdmin/Дерево в БД поверх перенаправления и без оставления пер…)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск


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

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

Как правило, хранение данных, имеющих древовидную структуру, организовывается в реляционной СУБД с использованием двух ключевых полей — первичного уникального ключа (обозначим его 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), при этом сервер не нагружен[1].

Если нужно выбрать дерево для десяти корневых сообщений — выборка с 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.

Примечания

  1. Имеется ввиду сервер БД. Физически дальнейшая обработка полученных данных может осуществляться на том же компьютере, но не средствами СУБД, а на языке программирования, на котором написана основная программа, например — PHP.