Участник:ArmorAdmin/Дерево в БД — различия между версиями
м (→Дерево в БД) |
(→Дерево в БД) |
||
Строка 7: | Строка 7: | ||
В компьютерных программах часто используется древовидное представление данных (например, в древовидном представлении очень удобно просматривать ход обсуждения какой-либо темы в процессе переписки или на форуме). | В компьютерных программах часто используется древовидное представление данных (например, в древовидном представлении очень удобно просматривать ход обсуждения какой-либо темы в процессе переписки или на форуме). | ||
− | Как правило, хранение данных, имеющих древовидную структуру, организовывается в реляционной СУБД с использованием двух ключевых | + | Как правило, хранение данных, имеющих древовидную структуру, организовывается в реляционной СУБД с использованием двух ключевых полей — первичного уникального ключа (обозначим его ID) и вторичного (PID), ссылающегося на ID ближайшего узла верхнего уровня (родителя). Если текущий узел корневой, в зависимости от реализации PID может быть равен −1, 0 или null. |
− | Если дерево небольшое, хранится в отдельной таблице и используется целиком (как правило такой вариант используется в вертикальном меню некоторых программ), то связка ID-PID прекрасно работает. Если же объём данных составляет десятки и сотни тысяч записей, а выбирать необходимо только какую-то часть дерева, тогда возникают проблемы с | + | Если дерево небольшое, хранится в отдельной таблице и используется целиком (как правило такой вариант используется в вертикальном меню некоторых программ), то связка ID-PID прекрасно работает. Если же объём данных составляет десятки и сотни тысяч записей, а выбирать необходимо только какую-то часть дерева, тогда возникают проблемы с производительностью — для выборки дерева из БД по связке ID-PID необходимо рекурсивно выполнить большое число SQL-запросов, что сильно нагружает сервер, или одним запросом выбрать все дерево и на сервере или клиенте программно отсечь лишние данные и построить дерево, что тоже очень затратно с точки зрения нагрузки на сервер. |
'''Рассмотрим возможный вариант решения проблемы.''' | '''Рассмотрим возможный вариант решения проблемы.''' | ||
− | Допустим, что в нашем случае для корневых узлов PID = | + | Допустим, что в нашем случае для корневых узлов PID = −1. |
Дополнительно вводим: | Дополнительно вводим: | ||
− | * индексированное поле rootID, которое ссылается на корневое сообщение ветки; | + | * индексированное поле rootID, которое ссылается на корневое сообщение ветки; |
− | * и текстовое уникальное индексированное поле path. | + | * и текстовое уникальное индексированное поле path. |
Следует заметить, что некоторые СУБД позволяют заводить текстовое поля практически без ограничения длины с возможностью их индексации, как это принято для строковых полей ограниченной длины. Если у нас такая СУБД, то path следует проиндексировать. | Следует заметить, что некоторые СУБД позволяют заводить текстовое поля практически без ограничения длины с возможностью их индексации, как это принято для строковых полей ограниченной длины. Если у нас такая СУБД, то path следует проиндексировать. | ||
− | Итак, поле path. В нем через точку вписаны ID всех узлов, начиная с root, для которых он является вложенным, включая ID самого узла, например так: | + | Итак, поле path. В нем через точку вписаны ID всех узлов, начиная с root, для которых он является вложенным, включая ID самого узла, например так: «2.34.456.» (с точкой в конце). |
Два дополнительных поля дают широкие возможности манипуляции данными с использованием простых запросов. Правда, на стороне клиента надо сделать несколько вариантов обработки, но производительность при этом нас не озадачивает. | Два дополнительных поля дают широкие возможности манипуляции данными с использованием простых запросов. Правда, на стороне клиента надо сделать несколько вариантов обработки, но производительность при этом нас не озадачивает. | ||
Если SQL-запросом необходимо выбрать ветку для заданного корня ID=5, то это делается так: | Если SQL-запросом необходимо выбрать ветку для заданного корня ID=5, то это делается так: | ||
− | |||
− | |||
− | + | <source lang="sql"> | |
+ | select * from tableName | ||
+ | where rootID = 5</source> | ||
− | + | В этом случае выстроить дерево на клиенте — дело техники (по связке ID, PID или по path), при этом сервер не нагружен<ref>Имеется ввиду сервер БД. Физически дальнейшая обработка полученных данных может осуществляться на том же компьютере, но не средствами СУБД, а на языке программирования, на котором написана основная программа, например — PHP.</ref>. | |
− | + | Если нужно выбрать дерево для десяти корневых сообщений — выборка с <code>PID = −1</code> и <code>LIMIT 10</code>, по каждому дополнительный запрос как в предыдущем варианте. То есть число запросов получается не по количеству сообщений в дереве, а по числу корневых сообщений + 1. | |
− | + | Самое хитрое — выборка части дерева не с корня, например для узла «5.12.33». | |
− | + | Можно просто выбирать: | |
− | (обратите внимание на точку, добавленную к коду перед знаком процента, без нее могут быть выбраны и записи с кодом | + | <source lang="sql"> |
+ | select * from tableName | ||
+ | where path like '5.12.33.%'</source> | ||
+ | |||
+ | (обратите внимание на точку, добавленную к коду перед знаком процента, без нее могут быть выбраны и записи с кодом «5.12.333», не имеющие отношения к нашей ветке) | ||
поскольку поле проиндексировано, то для начала строки индекс отработает. Если с индексом по длинному тексту проблема, возможен такой вариант: | поскольку поле проиндексировано, то для начала строки индекс отработает. Если с индексом по длинному тексту проблема, возможен такой вариант: | ||
− | <source lang="sql">where rootID = 5 and path like '5.12.33.%'</source> | + | <source lang="sql"> |
+ | select * from tableName | ||
+ | where rootID = 5 and path like '5.12.33.%'</source> | ||
− | При правильном оптимизаторе отработает выборка по проиндексированному root, после чего уже по ограниченному набору данных будет происходить | + | При правильном оптимизаторе отработает выборка по проиндексированному root, после чего уже по ограниченному набору данных будет происходить LIKE. |
== Примечания == | == Примечания == | ||
<references /> | <references /> |
Версия 14:22, 30 сентября 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, то это делается так:
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.