Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

Читайте также:
  1. Индексные файлы
  2. Файлы MIDI



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

 

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

Длина записи файла (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; Просмотров: 155; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.156.47.142
Генерация страницы за: 0.004 сек.