Индексные файлы
|
Полезная статья? Пожалуйста, поставьте "+"
Базы данных - Содержание
Индексные файлы (индексно-прямые, индексно-последовательные, В-деревья)
Индексные файлы могут представить как файлы состоящие из 2-х частей: индексная часть и основная часть. Различают 2 типа файлов:
- с плотным индексом или индексно-прямые файлы
- с неплотным индексом (неполным) или индексно – последовательные файлы
значение ключа – это значение первичного ключа
Для
индексно-прямых файлов поиск начинается в индексной области, где
применяется двоичный алгоритм поиска, потом путем прямой адресации
обращение к основной области по конкретному номеру записи.
Количество обращений к диску (при поиске записи):
Тn=log2 N+1
Например Длина записи LZ=12 байт. Количество записей в файлах KZ=100000
Размер блока LB=1024 байт
т.к. количество записей 100000, то для записи N нужно 4 байта, следовательно длина индексной записи LI: LI=LK+4=16 байт
1024/16=64
– количество индексных. записей в одном блоке 100000/64=1563 блоков
следовательно Tn=log21563+1=11+1=12 обращений к диску
Если нет
индексного пространства, то при произвольном хранении в основной области
100000/(1024/128)=12500 блоков – обращений к диску (времени просмотра
внутри блока пренебрегаем). Т.к. процесс происходит в оперативной
памяти.
Для индексно последовательный файлов – файлы хранятся в упорядоченном виде, следовательно Tn=log212500=14 обращений к диску.
Неплотный индекс строится для упорядоченных файлов. Индекс имеет вид:
Значение ключа 1-й записи блока № блока с этой записью
Пример
заполнения индексной и основной области при организации неплотного
индекса. Если для плотного индекса нужно было ссылаться на 100000
записей, то сейчас – при неплотном индексе требуется ссылаться на 12500
блоков, следовательно для ссылки (т.е. для адреса) достаточно 2 байта.
Следовательно, длина индексной записи:
LI=LK+2=12+2=14 байт
1024/14=73 – количество индексных записей в одном блоке 12500/73=172 – количество индексных блоков.
Tn=log2 172+1=8+1=9 – обращений к диску.
Следовательно организация неплотного индекса дает выигрыш в скорости по сравнению с плотным индексом.
Организация индексов в виде В-деревьев:
Идея:
построить индекс над уже существующим индексом (например неплотным
индексом). Область может быть рассмотрена как основной файл, над которым
снова строим неплотный индекс и т.д., пока не останется всего один
индексированный блок.
При вставке и удалении узлов производится реструктуризация дерева с тем, чтобы сохранить его сбалансированность.
|
| Категория: Базы данных | Добавил: Ni-Cd (09 Декабря 2011)
|
| Просмотров: 2265
| Рейтинг: 1.0/1 |
Добавлять комментарии могут только зарегистрированные пользователи. [ Регистрация | Вход ] |
|
| Онлайн |
Онлайн всего: 1 Гостей: 1 Пользователей: 0 |
| |
|
