4446
правок
R-дерево: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Постановка задачи
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Формулировка задачи и модель ввода-вывода | Формулировка задачи и модель ввода-вывода | ||
Пусть S – множество из N гиперкубов, параллельных осям, в пространстве | Пусть S – множество из N гиперкубов, параллельных осям, в пространстве <math>\mathbb{R}_d \;</math>. Одной из простейших операций к пространственной базе данных является ответ на оконные запросы на множестве S. Оконный запрос Q также представляет собой параллельный осям гиперкуб в пространстве <math>\mathbb{R}_d \;</math>, который предлагает вернуть все гиперкубы из S, имеющие пересечение с Q. Поскольку S, как правило, очень велико и пространственная база также имеет очень большой размер, задача состоит в разработке структуры данных с внешней памятью на дисках (в посвященной базам данных литературе такая структура часто называется индексом), позволяющей эффективно отвечать на подобные оконные запросы. Кроме того, при заданном множестве S структура данных должна быть эффективной в построении и поддерживать вставку и удаление объектов. | ||
| Строка 25: | Строка 25: | ||
Любое R-дерево занимает линейное число O(N/B) блоков на диске, однако у разных R-деревьев может быть разная стоимость запроса, обновления и построения. При анализе сложности оконных запросов наряду со значениями N, M и B также учитывается размер выходных данных T. | Любое R-дерево занимает линейное число O(N/B) блоков на диске, однако у разных R-деревьев может быть разная стоимость запроса, обновления и построения. При анализе сложности оконных запросов наряду со значениями N, M и B также учитывается размер выходных данных T. | ||
== Основные результаты == | == Основные результаты == | ||