Методы пространственного индексирования в СУБД

• Автор: Мартынов, Максим Геннадьевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Санкт-Петербург
• Количество страниц: 78 с.

Содержание
1 Введение
2 Пространственные методы доступа
2.1 Области применения
2.2 Типы хранимых данных
2.3 Пространственные запросы
2.4 Методы индексирования
2.4.1 Методы индексирования точечных объектов
2.4.2 Методы индексирования протяженных объектов
2.4.3 Пространственные деревья
2.5 11-деревья
3 Улучшения алгоритмов обработки И-дерева
3.1 Локальные координаты
3.2 Модификация алгоритма динамического удалешхя и вставки
3.3 Временный локальный клеточный индекс
4 Пространственное соединение с использованием Л-деревьев
4.1 Комбинированный алгоритм пространственного соединения
4.1.1 Алгоритм пространственного соединения, использующий свойство асимметрии чтения страниц
4.1.2 Алгоритм пространственного соединения, использующий попеременный спуск в деревьях
4.1.3 Комбинированный алгоритм

4.2 Клеточная эвристика
4.3 Использование ориентированных многоугольников
5 Использование алгоритмов пространственных методов для индексирования текстов
5.1 Индекс для инвертированных списков
5.2 Алгоритм обработки инвертированных списков
5.3 Оценка выигрыша в производительности
6 Заключение

1 Введение
Пространственные методы доступа [5, 48, 1] являются основой геоинфор-мационных систем, а также широко применяются в других областях, таких как временные базы данных [8], компьютерное зрение [27], базы знаний, САПР [7] и др., требующих многоатрибутного индексирования [48]. Важным требованием к таким системам является необходимость эффективной обработки очень больших объемов данных, имеющих пространственную природу, что делает необходимым использование специальных методов доступа к данным в таких системах.
Пространственные методы доступа — это методы физической организации данных, основанные на индексировании объектов в базах данных и других системах обработки информации, которые позволяют эффективно выполнять запросы, использующие отношения пространственной близости и вложенности объектов. Другими словами, пространственные методы индексирования позволяют производить быстрый поиск по значениям нескольких атрибутов сразу.
Наглядным примером такого поиска является нахождение объектов на карте, попадающих в заданный прямоугольник запроса.
Обычные методы индексирования — В+-деревья [25], различные варианты линейного хэширования — не подходят для таких систем. Они позволяют выполнять индексирование только по одному атрибуту, что делает их неэффективными для пространственных запросов, особенно если множество поиска очень велико.
Хранение линейных индексов по каждому атрибуту в отдельности

Метод Time Stor Qavr
Без клеточного индекса Клеточный индекс 2x2 Клеточный индекс 3x3 Клеточный индекс 4x4 100 68.4 8.1 83.3 68.4 8.3 79.6 69.2 8.7 77.3 70
Таб. 3.3: Тестирование временного локального клеточного индекса.
ческого удаления и вставки может получиться так, что удаленные записи попадут в тот же самый узел. Чтобы не создавать временный индекс без необходимости, при удалении записей не происходит создания индекса, а флаг /г сбрасывается. Если записи не попадают в тот лее узел, то при первом же участии этого узла в алгоритме добавления новой записи будет создан временный индекс при условии наличия свободного пространства для его размещения.
При добавлении нового объекта данных в дерево на каждом его уровне происходит выбор поддерева для вставки объекта. Для этого вычисляется ” расстояние” между пространственным ключом добавляемой записи и пространственными ключами всех записей текущего узла. При наличии временного индекса сначала определяются клетки, с которыми пересекается увеличенный в 8 раз пространственный ключ добавляемой записи, затем только записи, принадлежащие этим клеткам, участвуют в выборе поддерева. Параметр 8 выбирается эмпирически. Если выбранные клетки не содержат записей, то рассматриваются соседние с ними клетки.
Таблица 3.3 содержит результаты экспериментов по тестированию временного локального клеточного индекса.
Во всех методах 8 = 0.3. Остальные параметры экспериментов такие же как в предыдущем разделе. В таблице использованы следующие обозначения: Time — затраты процессорного времени в относительных единицах, Stor — коэффициент использования памяти, Qavr — усреднен-