Участник:ArmorAdmin/Дерево в БД — различия между версиями
м (→Дерево в БД) |
(→Дерево в БД) |
||
| Строка 27: | Строка 27: | ||
Если SQL-запросом необходимо выбрать ветку для заданного корня ID=5, то это делается так: | Если SQL-запросом необходимо выбрать ветку для заданного корня ID=5, то это делается так: | ||
| − | < | + | <source lang="sql">where rootID=5</source> |
В этом случае выстроить дерево на клиенте — дело техники (по связке ID, PID или по path), при этом сервер не нагружен<ref>Имеется ввиду сервер БД. Физически дальнейшая обработка полученных данных может осуществляться на том же компьютере, но не средствами СУБД, а на языке программирования, на котором написана основная программа, например — PHP.</ref>. | В этом случае выстроить дерево на клиенте — дело техники (по связке ID, PID или по path), при этом сервер не нагружен<ref>Имеется ввиду сервер БД. Физически дальнейшая обработка полученных данных может осуществляться на том же компьютере, но не средствами СУБД, а на языке программирования, на котором написана основная программа, например — PHP.</ref>. | ||
| Строка 37: | Строка 37: | ||
Можно просто выбирать: | Можно просто выбирать: | ||
| − | < | + | <source lang="sql">where path like '5.12.33.%'</source> |
| + | |||
| + | (обратите внимание на точку, добавленную к коду перед знаком процента, без нее могут быть выбраны и записи с кодом "5.12.333", не имеющие отношения к нашей ветке) | ||
поскольку поле проиндексировано, то для начала строки индекс отработает. Если с индексом по длинному тексту проблема, возможен такой вариант: | поскольку поле проиндексировано, то для начала строки индекс отработает. Если с индексом по длинному тексту проблема, возможен такой вариант: | ||
| − | < | + | <source lang="sql">where rootID = 5 and path like '5.12.33.%'</source> |
При правильном оптимизаторе отработает выборка по проиндексированному root, после чего уже по ограниченному набору данных будет происходить like. | При правильном оптимизаторе отработает выборка по проиндексированному root, после чего уже по ограниченному набору данных будет происходить like. | ||
Версия 10:14, 29 сентября 2009
Дерево в БД
- Автор(ы): --Чобиток Василий 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, то это делается так:
where rootID=5В этом случае выстроить дерево на клиенте — дело техники (по связке ID, PID или по path), при этом сервер не нагружен[1].
Если нужно выбрать дерево для десяти корневых сообщений — выборка с PID = -1 и LIMIT 10, по каждому дополнительный запрос как в предыдущем варианте. Т.е. число запросов получается не по количеству сообщений в дереве, а по числу корневых сообщений + 1.
Самое хитрое — выборка части дерева не с корня, например для узла "5.12.33".
Можно просто выбирать:
where path like '5.12.33.%'(обратите внимание на точку, добавленную к коду перед знаком процента, без нее могут быть выбраны и записи с кодом "5.12.333", не имеющие отношения к нашей ветке)
поскольку поле проиндексировано, то для начала строки индекс отработает. Если с индексом по длинному тексту проблема, возможен такой вариант:
where rootID = 5 and path like '5.12.33.%'При правильном оптимизаторе отработает выборка по проиндексированному root, после чего уже по ограниченному набору данных будет происходить like.
Примечания
- ↑ Имеется ввиду сервер БД. Физически дальнейшая обработка полученных данных может осуществляться на том же компьютере, но не средствами СУБД, а на языке программирования, на котором написана основная программа, например — PHP.
