Организация индексов в виде В-деревьев

Построение В-деревьев связано с простой идеей создания индекса над уже построенным индексом. Например, при построении индексно-последовательного файла сама индексная область может быть рассмотрена как основной файл, над которым можно построить неплотный индекс, и так далее, пока индексную область не будет представлять только один блок.

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

Такие деревья называют сбалансированными (путь от корня до любого листа одинаков) Таким образом, термин В -дерево происходит от английского balance (баланс). Пример организации В-дерева представлен на рис.30.

Использование техники B-деревьев в настоящее время, скорее всего, является наиболее популярным подходом к организации индексов в базах данных. С точки зрения внешнего логического представления, B-дерево - это сбалансированное, сильно ветвистое дерево во внешней памяти. Ветвистость дерева - это свойство каждого узла дерева ссылаться на большое число узлов-потомков. С точки зрения физической организации, B-дерево представляется как мультисписочная структура страниц внешней памяти, то есть каждому узлу дерева соответствует блок внешней памяти (страница, см. п.7.3.2.). Внутренние и листовые страницы обычно имеют разную структуру.

Поиск в B-дереве - это прохождение от корня к листу в соответствии с заданным значением ключа.

B-деревья универсальны и обеспечивают хорошую скорость доступа как при просмотрах по диапазонам, так и при выборке единичной записи по значению ключа, однако характеризуются относительно большим объемом памяти для хранения и затратами на поддержание в актуальном состоянии, включающими обычно балансировку дерева.

Инвертированный файл (доступ по неключевым атрибутам)

Рассмотренные выше методы доступа осуществляют поиск записей по значению первичного ключа. Однако выполнение операции типа ПОЛУЧИТЬ НЕКОТОРЫЕ предполагает указание критерия отбора экземпляров записей по значениям одного или нескольких неключевых атрибутов (часто называемых вторичным и ключами).Заметим, что соответствующий запрос на языке SQL включает предложение WHERE.

Основным методом организации поиска по значениям неключевых атрибутов является инвертирование файла.

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

Список указателей доступа представляет собой физически последовательный список указателей на записи, содержащие идентичные значения соответствующего атрибута.

В наиболее распространенном варианте используется двухуровневый индекс. Схема организации инвертированного файла представлена на рис.31.

Частично инвертированный файл инвертируется по выборочному количеству неключевых атрибутов.

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

Выше рассмотрено построение индексов из одиночных атрибутов (типов элементов данных). Очевидно, что можно использовать составные индексы, элементы которых соответствуют значениям сцепленных элементов различных типов.

 

 

 

Рис.30. Схема организации В-дерева

Использование битовых шкал

Этот вид индекса определяется на множестве записей, в котором каждому свойству записей ставится в соответствие битовая строка (статья индекса). Количество битов в строке равно общему количеству записей файла, и соответствующий данной записи бит принимает единичное значение тогда и только тогда, когда запись обладает рассматриваемым свойством. Очевидно, что при этом записи файла СУБД пронумеровываются, так что соответствие между битами строки и записями устанавливается по этим внутрисистемным номерам. Свойство может иметь различный смысл, например, может означать, что некоторый атрибут записи имеет данное значение.

Пример 1. Пусть основной файл содержит следующие записи:

 

	S01	Иванов	Томск
	S02	Петров	Томск
	S03	Сидоров	Кемерово
	S04	Кузнецов	Барнаул
	S05	Петров	Омск

 

Значения элементов данных в полях записей отображают значения:

Поле1 – внутрисистемных номеров записей,

Поле2 – атрибута - первичного ключа,

Поле3 – атрибута – Фамилия_поставщика,

Поле4 – атрибута - Город, где живет поставщик.

Сформируем битовые строки, соответствующие следующим свойствам:

 

Свойство	Статья (битовая строка)
Фамилия_поставщика = “Петров”	0 1 0 0 1
Город = ”Томск”	1 1 0 0 0

Такая организация индекса имеет два важных достоинства:

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

2. Битовое представление индекса позволяет с высокой эффективностью выполнять операции выборки (селекции) записей по сложным логическим критериям, содержащим логические связки AND, OR и NOT, с помощью поразрядных логических операций над битовыми строками.

Возможны различные другие схемы организации битовых индексов. Например, можно статьи индекса ставить в соответствие не свойствам записей, а самим записям. При этом статья индекса будет содержать уникальный идентификатор записи (не обязательно соответствующий первичному ключу) и битовую строку, позиции которой будут соответствовать значениям различных свойств.

Пример 2. По этой схеме сформируем битовые строки для записей файла из Примера 1, соответствующие следующим свойствам:

Свойство 1. Фамилия _ поставщика = “Петров”

Свойство 2. Город = “Томск”

Состав индекса:

 

Номер статьи	Значение уникального идентификатора	Битовая строка
	S01	0 1
	S02	1 1
	S03	0 0
	S04	0 0
	S05	1 0

 

Очевидно, что такая организация битовых шкал освобождает СУБД от необходимости перенумеровывать записи файла.

Заметим, что формирование битовой шкалы по второй схеме является в некотором роде транспонированием битовой шкалы, составленной по первой схеме.

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

Замечание. В правильно спроектированной базе данных каждая таблица содержит первичный ключ, что означает автоматическое наличие индекса, построенного самой СУБД.

Данный обзор показывает, что современные СУБД предоставляют достаточно широкий набор различных методов доступа, которые чаще всего являются теми или иными видами индексирования — способа отображения ключа индексирования в адрес хранимой записи (включая и хэширование). Наиболее часто используемыми являются индексные структуры на основе B-дерева (B–tree); на основе хэш-функции или хеширование (hashing); на базе битовых шкал или индексов (bitmap). Индекс может служить различным целям: для ускорения доступа к записям одной таблицы и для ускорения операций соединения, тогда он называется индексом соединения. Если в качестве ключа индексирования используется некоторая функция атрибутов таблицы, такой индекс называют «основанным на функции» (function-based).

 

 

Рис.31. Схема механизма инвертирования