Древовидные структуры для многомерных данных 1)Индексы с несколькими ключами 2)Kd-деревья 3)Деревья квадрантов 4)R-деревья

Индексы с несколькими ключами

Эффективность Индексы второго и более уровней могут быть очень маленькими, и их часто заменяются простыми таблицами. Запросы на равенство по первому атрибуту – высокая эффективность Запросы на равенство по внутренним атрибутам – требуют обращения к каждому подчиненному индексу Запросы в диапазонах значений – неплохая эффективность, если входящие индексы также поддерживают запросы на диапазоны значений Поиск ближайших соседей – эффективность такая же, как и в случае поиска диапазона значений

Kd-деревья Kd-дерево – это бинарное дерево. Каждой его промежуточной вершине поставлены в соответствие некоторые атрибуты, его конкретное разделяющее значение и указатели, адресующие левую и правую половины. Его листья представляют блоки, способные содержать такое количество записей, какое обусловлено физическим объемом блока.

Эффективность Запросы на совпадение отдельных координат – просмотр до листьев, из их общего числа n. Средняя длина пути – log 2 n. Проблема – большее, по сравнению с B-деревом число операций чтения с диска. Решения: 1) множественное ветвление 2) группирование промежуточных вершин по блокам

Деревья квадрантов В деревья квадрантов каждая промежуточная вершина соответствует определенному k-мерному параллелепипеду если пространство имеет размерность – k. Листья дерева – это таблицы конкретных значений координат точек.

R-деревья R-дерево – это многомерный аналог B- деревьев. Каждая его промежуточная вершина соответствует некоторой области данных и содержит в себе информацию о вложенных в нее подобластях – дочерних вершинах. Листья – это таблицы точек.