Физическая организация файлов в БД. Индексация

	Значение ключа в первом записи блока	Номер блока с этой записью

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

Рисунок 8 - Пример заполнения индексной и основной области при организации неплотного индекса.

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

Сначала определим размер индексной  записи. Если ранее ссылка рассчитывалась исходя из того, что требовалось ссылаться на 100000 записей, то теперь нам требуется ссылаться всего на 12 500 блоков, поэтому для ссылки достаточно двух байт. Тогда длина индексной записи будет равна:

LI = LK + 2 = 14 + 2 - 14 байт.

Тогда количество индексных записей  в одном блоке будет равно:

KIZB = LB/LI = 1024/14 = 73 индексные записи  в одном блоке.

Определим количество индексных блоков, которое необходимо для хранения требуемых индексных записей:

KIB = KBO/KZIB = 12500/73 = 172 блока.

Тогда время доступа по прежней  формуле будет определяться:

Т_поиска = log₂KIB + 1 = log₂172 + 1=8+1=9 обращений к диску.

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

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

Здесь механизм включения новой  записи принципиально отличен от ранее рассмотренного. Здесь новая  запись должна заноситься сразу в  требуемый блок на требуемое место, которое определяется заданным принципом упорядоченности на множестве значений первичного ключа. Поэтому сначала ищется требуемый блок основной памяти, в который надо поместить новую запись, а потом этот блок считывается, затем в оперативной памяти корректируется содержимое блока и он снова записывается на диск на старое место. Здесь, так же как и в первом случае, должен быть задан процент первоначального заполнения блоков, но только применительно к основной области. В MS SQL server этот процент называется Full-factor и используется при формировании кластеризованных индексов. Кластеризованными называются как раз индексы, в которых исходные записи физически упорядочены по значениям первичного ключа. При внесении новой записи индексная область не корректируется.

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

Т_{добавлений} ⁼ log₂N +1 + 1 обращений.

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

1.6 Организация индексов в виде B-tree (В-деревьев)

Калькированный термин «В-дерево», в котором смешивается английский символ «В» и добавочное слово  на русском языке, настолько устоялся в литературе, посвященной организации физического хранения данных, что я не решусь его корректировать.

Встретив как-то термин «B-дерево», я долго его трактовала, потому что привыкла уже к устоявшемуся обозначению. Поэтому будем работать с этим термином.

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

Мы в общем случае получим  некоторое дерево, каждый родительский блок которого связан с одинаковым количеством подчиненных блоков, число которых равно числу  индексных записей, размещаемых в одном блоке. Количество обращений к диску при этом для поиска любой записи одинаково и равно количеству уровней в построенном дереве. Такие деревья называются сбалансированными (balanced) именно потому, что путь от корня до любого листа в этом древе одинаков. Именно термин «сбалансированное» от английского «balanced» — «сбалансированный, взвешенный» и дал название данному методу организации индекса.

Построим подобное дерево для нашего примера и рассчитаем для него количество уровней и, соответственно, количество обращений к диску.

На первом уровне число блоков равно  числу блоков основной области, это  нам известно, — оно равно 12 500 блоков. Второй уровень образуется из неплотного индекса, мы его тоже уже строили и вычислили, что количество блоков индексной области в этом случае равно 172 блокам. А теперь над этим вторым уровнем снова построим неплотный индекс.

Мы не будем менять длину индексной  записи, а будем считать ее прежней, равной 14 байтам. Количество индексных  записей в одном блоке нам тоже известно, и оно равно 73. Поэтому сразу определим, сколько блоков нам необходимо для хранения ссылок на 172 блока.

КIВ₃ = KIB₂/KZIB = 172/73 = 3 блока

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

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

Т_д= R_уравн. =4 

1 уровень 12500 блоков

2 уровень 172 блоков

3 уровень 3 блоков

4 уровень 1 блоков

Рисунок 9 - Построенное В-дерево.

Механизм добавления и удаления записи при организации индекса  в виде В-дерева аналогичен механизму, применяемому в случае с неплотным  индексом.

И наконец, последнее, что хотелось бы прояснить, — это наличие вторых названий для плотного и неплотного индексов.

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

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

1.7 Индексирование в базах данных

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

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

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

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

1.7.1 Типы индексов

Для ускорения доступа к данным применяется несколько типов индексов. Основные из них, перечислены ниже:

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

Файл может иметь не больше одного первичного индекса или одного индекса кластеризации, но дополнительно к ним может иметь несколько вторичных индексов. Индекс может быть разреженным (sparse) или плотным (dense). Разреженный индекс содержит индексные записи только для некоторых значений ключа поиска в данном файле, а плотный индекс имеет индексные записи для всех значений ключа поиска в данном файле. Ключ поиска для индекса может состоять из нескольких полей.

1.7.2 Индексно-последовательные файлы

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

• первичная область хранения;
• отдельный индекс или несколько индексов;
• область переполнения.

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

1.7.3 Вторичные индексы

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

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

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

1.7.4 Многоуровневые индексы

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