Индексы

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

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

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

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

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

N1

Ключ1

N2

………..

Nn

Ключ n

При этом выдерживаются следующие свойства:

ключ 1 <= ключ 2 …. <=ключ n

Ni – является идентификатором страницы внешней памяти, в роли идентификатора в общем случае выступает адрес страницы. В странице дерева Ni находятся ключи k со значениями:

ключ(i-1)<=k<=ключ i

Листовые страницы связаны одно- или двунаправленным списком.

Поиск в В-дереве – это проходение от корня к листу в соответствии с заданным значением ключа. Т.к. деревья сильно ветвисты и сбалансированы, то для выполнения поиска по любому значению ключа потребуется одно и то же и обычно небольшое число обменов с внешней памятью. Более точно если во внутренней странице помещается n ключей, то при хранении m записей требуется дерево глубиной log_nm. Если m достаточно велико, то глубина дерева невелика и выполняется быстрый поиск.

Основной «изюминкой» В-дерева является автоматическое поддержание свойства сбалансированности. Рассмотрим, как это выполняется при занесении новой записи:

1. Поиск листовой страницы. Фактически производится обычный поиск по ключу, т.е. в корневой странице В-дерева ищется ключи, совпадающий по значению или ближайшее большее значение. Далее выполняется переход к странице, на которой должен содержаться этот ключ, если эта страница является внутренней страницей, на ней опять производится поиск равного или ближайшего большего значения ключа и так далее до тех пор, пока не будет достигнута листовая страница. На листовой странице так же производится поиск соответствующего значения ключа, если это значение найдено, то СУБД получает список идентификаторов картежей, в которых находятся записи с заданным значением ключа.

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

3. Если после выполнения вставки новой записи размер используемой части буфера не превосходит размеры страницы, то на этом выполнение операции занесения заканчивается. Буфер может быть немедленно вытолкнут во внешнюю память или временно сохранен в ОП, в зависимости от политики управления буферами.

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

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

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

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

1. Упреждающее расщепление, т.е. расщепление страницы не при ее переполнении, а несколько раньше, когда степень ее заполнения достигает некоторого уровня.

2. Переливание, т.е. поддержание равновесного заполнения соседних страниц.

3. Слияние три в две. Т.е. порождение двух листовых страниц на основе содержимого трех соседних.

Дата добавления: 2014-01-04