Участник:ArmorAdmin/Дерево в БД — различия между версиями
(→Дерево в БД) |
|||
Строка 1: | Строка 1: | ||
− | + | {{DISPLAYTITLE:Дерево в реляционной базе данных}} | |
{{Библиография | {{Библиография | ||
|Автор = [[Участник:ArmorAdmin|Чобиток Василий]] 14:21, 11 июля 2007 (EEST) | |Автор = [[Участник:ArmorAdmin|Чобиток Василий]] 14:21, 11 июля 2007 (EEST) |
Версия 16:21, 30 июня 2010
- Автор(ы): Чобиток Василий 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.
Примечания
- ↑ Имеется ввиду сервер БД. Физически дальнейшая обработка полученных данных может осуществляться на том же компьютере, но не средствами СУБД, а на языке программирования, на котором написана основная программа, например — PHP.