Индексно-прямые файлы

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

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

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

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

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

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

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

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

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