Файлы с плотным индексом, или индексно-прямые файлы

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

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

Длина записи файла (LZ) — 128 байт. Длина первичного ключа (LZ) — 12 байт. Количество записей в файле (К2) — 100000. Размер блока (LZ) — 1024 байт.

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

и = ПС + 4 = I4 + 4 = 16 байт.

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

КI2В = LB/LI = 1024/16 = 64 индексных записи в одном блоке.
Теперь определим необходимое количество индексных блоков:
КIВ - К2/К2IВ = 100000/64 - 1563 блока.

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

А теперь мы уже можем вычислить максимальное количество обращений к дис­ку при поиске произвольной записи:

Тпоиска = log2КIВ + 1 = log21563 +1 = 11 + 1 = 12 обращений к диску.

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

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

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

КВО = К2/(LB/LZ) - 100000/(1024/128) - 12500 блоков.

И это означает, что максимальное время доступа равно 12500 обращений к диску. Да, действительно, выигрыш существенный.

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

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

Рис. 9.7. Пример организации файла с плотным индексом

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

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

Тдобавления = log2 +1 + 1 + 1.

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

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

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

Дата добавления: 2015-05-09