Упорядоченный файл
Кортежи в файле можно отсортировать по значениям одного или нескольких атрибутов и таким образом образовать набор данных, упорядоченный по некоторому ключу. Получим упорядоченный (последовательный) файл. Атрибут (или набор атрибутов), по которому сортируется файл, называется атрибутом упорядочения. Если атрибут упорядочения является также ключом доступа к файлу (и поэтому гарантируется наличие в каждом кортеже уникального значения этого атрибута), оно называется ключом упорядочения для данного файла.
Для получения кортежа из упорядоченного файла можно использовать, например, алгоритм бинарного поиска.
Операции вставки и удаления кортежей в отсортированном файле усложняются в связи с необходимостью поддерживать установленный порядок записей. Для вставки нового кортежа нужно определить его расположение в указанном порядке, а затем найти свободное место для вставки. Если на нужной странице достаточно места для размещения нового кортежа, то потребуется переупорядочить кортежи только на этой странице, после чего вывести ее на диск. Если же свободного места недостаточно, то потребуется переместить один или несколько кортежей на следующую страницу. На следующей странице также может не оказаться достаточно свободного места, и из нее потребуется переместить некоторые кортежи на следующую страницу и т. д.
Таким образом, вставка кортежа в начало большого файла может оказаться очень длительной процедурой. Для решения этой проблемы часто используется временный неотсортированный файл, ко-
торый называется файлам переполнения (overflow file) или файлом транзакции (transaction file).
При этом все операции вставки выполняются в файле переполнения, содержимое которого периодически объединяется с основным отсортированным файлом. Следовательно, операции вставки выполняются более эффективно, но выполнение операций извлечения данных немного замедляется: если кортеж не найден во время бинарного поиска в отсортированном файле, то приходится выполнять линейный поиск в файле переполнения. И наоборот, при удалении кортежа необходимо реорганизовать файл, чтобы удалить пустующие места.
Упорядоченные файлы редко используются для хранения информации баз данных, за исключением тех случаев, когда для файла организуется первичный индекс.
8.4. Индексирование
Индекс — это вспомогательная структура данных, помогающая СУБД быстрее обнаруживать отдельные кортежи в файле, сократив тем самым время выполнения запросов на чтение, но при этом замедляется процесс добавления данных в силу необходимости поддерживать структуру индекса.
Определение 4. Индексом называется отображение IpAq, ставящее в однозначное соответствие значению атрибута (или множества атрибутов) A некоторое значение, по которому можно определить соответствующие этому значению кортежи.
В общем случаем имеем отображение множества значений атрибута(ов) во множество кортежей. Структура индекса связана с определенным ключом поиска и содержит записи, состоящие из ключевого значения и адреса кортежа в файле, содержащего это ключевое значение. При этом файл, содержащий кортежи, называется (индексированным) файлом данных, а файл, содержащий индексные записи для файла данных, — индексным файлом. Индекс и данные могут храниться и в одном файле. Значения в индексном файле упорядочены по полю индексирования, которое обычно строится
на базе одного атрибута.
Одноуровневый индекс представляет собой линейную совокупность значений одного или нескольких полей записи. На практике он используется только в простейших случаях, когда количество индексируемых записей невелико. В более сложных случаях индекс занимает много памяти (иногда – несколько страниц), и возникает задача минимизации доступа к нему. Тогда индекс разбивается на несколько иерархических уровней, что позволяет ускорить поиск требуемого
51
значения. Особенно эффективной является организация многоуровневых индексов в виде сбалансированных деревьев (B-деревьев, B+-деревьев и др.), в которых все пути от корня к листьям имеют одинаковую длину.
Можно выделить следующие типы индексов:
•Первичный индекс — в качестве атрибута упорядочивания выступает потенциальный ключ (обычно первичный) индексируемого отношения, а файл данных последовательно упорядочивается по этому ключу.
•Вторичный индекс — индексирование ведется по любому (обычно неключевому) атрибуту(ам), а сами индексные записи ссылаются на множество или диапазон кортежей (возможно одного). Обычно используются вместе с первичным индексом — в этом случае упорядочивание ведется именно по атрибуту(ам) первичного индекса, а не вторичного.
Файл может иметь не больше одного первичного индекса, но дополнительно к ним может иметь несколько вторичных индексов.
Еще индексы можно классифицировать как ibразреженные (sparse) или плотные (dense). Разреженный индекс содержит индексные записи только для некоторых значений ключа поиска в данном файле, а плотный индекс имеет индексные записи для всех значений ключа поиска в данном файле.
Индексно-прямой метод доступа
Виндексно-прямых файлах (или файлах с плотным индексом) индекс является первичным
иплотным. В таких файлах основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а каждая индексная запись представляет из себя пару <Значение_ключа, Указатель_на_кортеж>, где в качестве указателя можно использовать либо но-
мер слота (в случае, если кортежи и индексы в одном файле), либо пару идентификатор страницы и номер слота на ней.
Поиск по проиндексированному первичному ключу происходит в индексной файле, где применяется двоичный алгоритм поиска индексной записи, а потом путем прямой адресации происходит обращение к файлу данных (или области данных, если всё в одном файле) уже по конкретному номеру записи.
При операции добавления кортежа осуществляется запись в конец основной области. В индексной области необходимо произвести занесение информации в конкретное место, чтобы не нарушать упорядоченности. Поэтому вся индексная область файла разбивается на блоки и при начальном заполнении в каждом блоке остается свободная область (процент расширения).
После определения блока, в который должен быть занесен индекс, этот блок копируется в оперативную память, там он модифицируется путем вставки в нужное место новой записи и, измененный, записывается обратно на внешний носитель информации.
Естественно, в процессе добавления новых записей процент расширения постоянно уменьшается. Когда исчезает свободная область, возникает переполнение индексной области. В этом случае возможны два решения:
а) перестроить заново индексную область — для этого требуется дополнительное время; б) организовать область переполнения для индексной области, в которой будут храниться не по-
местившиеся в основную область записи, — но это приведет к увеличению времени доступа к произвольному кортежу и потребует организации дополнительных ссылок в блоках на область переполнения.
Именно поэтому при проектировании физической базы данных так важно заранее как можно точнее определить объемы хранимой информации, спрогнозировать ее рост и предусмотреть соответствующее расширение области хранения.
При удалении кортежа возникает следующая последовательность действий: запись в основной области помечается как удаленная (отсутствующая), в индексной области соответствующий индекс
52
уничтожается фактически, то есть записи, следующие за удаленной записью, перемещаются на ее место, и блок, в которой хранился данный индекс, заново записывается на диск.
Индексно-последовательный метод доступа
В индексно-последовательных файлах (или файлы с разреженным индексом; Indexed Sequential Access Method — ISAM) используются разреженные и первичные индексы. Является усовершенствованным вариантом индексно-прямого метода доступа.
Неплотный индекс строится именно для упорядоченных файлов. Для этих файлов используется принцип внутреннего упорядочения для уменьшения количества хранимых индексов. Структура записи индекса для таких файлов имеет следующий вид:
Значение ключа первого кортежа блока Указатель на блок
Вблоках так же резервируется свободное пространство (процент расширения) для новых индексов, которые образовываются при добавлении кортежей. Процент первоначального заполнения должен быть задан на стадии физического проектирования в зависимости от поведения данных в данном отношении (частота и вероятность вставки/удаления и прочее). Заметим, что в роли блоков могут выступать сами страницы с данными в силу их упорядоченности по проиндексированному атрибуту, что ускоряет доступ к кортежам (без посредников).
Время сортировки больших файлов весьма значительно, но поскольку файлы поддерживаются сортированными с момента их создания, накладные расходы в процессе добавления новой информации будут гораздо, меньше.
Втакой организации индекса новый кортеж должен заноситься сразу в требуемый блок на требуемое место, которое определяется заданным принципом упорядоченности на множестве значений первичного ключа. Поэтому сначала ищется требуемый блок основной памяти, в который надо поместить новый кортеж, а потом этот блок считывается, затем в оперативной памяти корректируется содержимое блока и он снова записывается на диск на старое место.
Уничтожение кортежа происходит путем ее физического удаления из основной области, при этом индексная область обычно не корректируется, даже если удаляется первая запись блока. Поэтому количество обращений к диску при удалении записи такое же, как и при добавлении новой записи.
Обычно при индексно-последовательном методе доступа количество индексных записей фиксировано, т. е. структура индекса остается неизменной — либо нужно полностью его перестраивать, что может дорого стоить, а значит, должно быть как можно реже.
Индекс на основе B+-деревья
B+-деревья отличаются от обычных B-деревьев тем, что нелистовые узлы всегда индексы, а листовые — страницы, содержащие кортежи со значением проиндексированного атрибута между соответствующими соседними значениями индекса, т. е. B+-дерево заканчивается листьями «раньше» B-дерева, не доходя до отдельных кортежей.
В общем, внутренний узел B+-дерева имеет вид:
pointer1 key1 pointer2 pointer2d 1 key2d 1 pointer2d
где key1 ď key2 ď : : : ď key2d 1 и в каждом внутреннем узле поддерева, на который ссылается указатель pointeri, находится ключи со значением из отрезка rkeyi 1; keyis.
Листовые узлы можно формировать по-разному. Например, так:
key1 list1 keyk listk
где key1 ă ă keyk, listi — упорядоченный список идентификаторов кортежей (tid), у которых индексируемый атрибут принимает значение keyi, и при этом листовые узлы связаны одноили двусвязным списком.
53
Поиск в B+-дереве – это прохождение от корня к листу в соответствии с заданным значением ключа. Заметим, что поскольку B+-деревья являются сильно ветвистыми и сбалансированными, для выполнения поиска по любому значению ключа потребуется одно и то же (и обычно небольшое) число обменов с внешней памятью.
Ключевым свойством B+-деревьев (как и B-деревьев) является автоматическое поддержание свойства сбалансированности при добавлении и удалении кортежей.
При занесение нового кортежа выполняются следующие действия.
•Поиск листовой страницы. Фактически, производится обычный поиск по ключу. Если в B+- дереве не содержится ключ с заданным значением, то будет получен номер страницы, в которой ему надлежит содержаться, и соответствующие координаты внутри страницы.
•Помещение записи на место. Естественно, что вся работа производится в буферах оперативной памяти. Листовая страница, в которую требуется занести запись, считывается в буфер, и в нем выполняется операция вставки. Размер буфера должен превышать размер страницы внешней памяти.
•Если после выполнения вставки новой записи размер используемой части буфера не превосходит размера страницы, то на этом выполнение операции занесения записи заканчивается. Буфер может быть немедленно вытолкнут во внешнюю память или временно сохранен в основной памяти в зависимости от политики управления буферами.
•Если же возникло переполнение буфера (т. е. размер его используемой части превосходит размер страницы), то выполняется расщепление страницы. Для этого запрашивается новая страница внешней памяти, используемая часть буфера разбивается примерно пополам (так, чтобы вторая половина также начиналась с ключа), и вторая половина записывается во вновь выделенную страницу, а в старой странице модифицируется значение размера свободной памяти. Естественно, модифицируются ссылки по списку листовых страниц.
•Чтобы обеспечить доступ от корня дерева к заново заведенной странице, необходимо соответствующим образом модифицировать внутреннюю страницу, являющуюся предком ранее существовавшей листовой страницы, т. е. вставить в нее соответствующее значение ключа и ссылку на новую страницу. При выполнении этого действия может снова произойти переполнение теперь уже внутренней страницы, и она будет расщеплена на две. В результате потребуется вставить значение ключа и ссылку на новую страницу во внутреннюю страницу-предка выше по иерархии и т. д.
•Предельным случаем является переполнение корневой страницы B+-дерева. В этом случае она тоже расщепляется на две, и заводится новая корневая страница дерева, т. е. его глубина увеличивается на единицу.
При удалении кортежа выполняются следующие действия.
•Поиск записи по ключу. Если запись не найдена, то удалять ничего не нужно.
•Реальное удаление записи в буфере, в который прочитана соответствующая листовая страница.
•Если после выполнения этой подоперации размер занятой в буфере области оказывается таковым, что его сумма с размером занятой области в листовых страницах, являющихся левым или правым братом данной страницы, больше, чем размер страницы, операция завершается.
•Иначе производится слияние с правым или левым братом, т.е. в буфере производится новый образ страницы, содержащей общую информацию из данной страницы и ее левого или правого брата. Ставшая ненужной листовая страница заносится в список свободных страниц. Соответствующим образом корректируется список листовых страниц.
•Чтобы устранить возможность доступа от корня к освобожденной странице, нужно удалить соответствующее значение ключа и ссылку на освобожденную страницу из внутренней страницы — ее предка. При этом может возникнуть потребность в слиянии этой страницы с ее левым или правым братом и т.д.
54