Киберфак – бесплатно скачать презентации PowerPoint, лекции, рефераты, шпоры, курсовые cyberfac logo
cyberfac.ru
На главную | Регистрация | Вход
  Статьи  
Главная » Статьи » Базы данных » Базы данных

Индексные файлы

Полезная статья? Пожалуйста, поставьте "+"
Базы данных - Содержание
Индексные файлы (индексно-прямые, индексно-последовательные, В-деревья)
Индексные файлы могут представить как файлы состоящие из 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)
Просмотров: 1724 | Рейтинг: 1.0/1
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
  Полезные материалы  

В нашем каталоге файлов можно найти много полезной информации. Также советуем заглянуть в каталог статей: в нем есть полезные статьи по темам: Экономика предприятия, Общая экономика, Финансы и Кредит, также Словарь терминов по экономике, Маркетинг, Бухучет и Мировая экономика
Также есть полезная страница Факультеты МИФИ, которая расскажет о том, какие есть в МИФИ факультеты.
Меню
 

Навигация
Базы данных [64]
 

Поиск
 

Онлайн
Онлайн всего: 1
Гостей: 1
Пользователей: 0
 

Статистика


Рейтинг@Mail.ru

 


2007 - 2018 © Ni-Cd. All Rights Reserved