Физическое представление данных, страница 7

Таким образом минимальная оценка такова. Если справочник содержит один блок нужен один доступ – для получения указателя. Еще один доступ – для получения блока с записью (предполагается, что записи находятся в одном блоке).

Еще один доступ нужен при операциях удаления и модификации. Итак для хеш – функции Кф ≥ 3.

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

Индексные файлы, это файлы, состоящие из основного файла, в котором размещаются записи индекса – файла, в котором размещаются в сортированные первичные ключи основного файла и ссылки на место расположения записей основного файла.

В зависимости от организации индексной и основной областей различают 2 типа файлов, с плотным индексом и неплотным индексом.

У этих файлов есть еще дополнительные названия:

Файлы с плотным индексом называются также индексно – прямыми файлами, а файлы с неплотным индексом – индексно – последовательными файлами смысл этого наименования мы уточним позже.

Неплотные индексы

Файлы с неплотным индексом имеют сортированные записи основного файла расположенные в основной области памяти блоках.

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

Блок I2

Блок I1

Значение ключей 1 записи каждого заполненного блока основной записи размещаются в сортированном виде в блоках индексной области памяти I1÷Im . В этих записях размещаются  ссылки на основную запись.

Быстродействие индексных файлов определяется стратегиями поиска. Рассмотрим стратегии поиска и их скоростные характеристики.

Стратегии поиска

1.  Линейный поиск

При поиске в индексных файлах с неплотным индексом необходимо ввести условие обработки блока индексного файла.

Пусть заданы блоки индексного файла в следующем виде:

Ключ       Адрес ссылки

Нам необходимо найти запись с ключом V2.  В этом случае в оперативную память загружается тот блок, для которого

V1< V2 <V3

И для ключа V1используют термин «ключ V1 покрывает V2».

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

Линейный поиск в индексном файле гораздо эффективнее линейного поиска в основном файле. Рассмотрим это: Пусть в основном файле содержится всего записей  - m2 в блоке основного файла  - Сгл – записей а в блоке индексного файла содержится  - Син записей.

В этом случае в основном  файле будет

Mгл/ Сгл – блоков

А в индексном файле.

Будет (Mгл/ Сгл)/ Син– блоков

т.к. Mгл/ Сгл – это количество записей в индексном файле.

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

Сравним скоростные характеристики поиска при линейной стратегии в простом файле и индексном файле с неплотным индексом.

Если поиск равновероятностный, если у нас нет индексного файла то там необходимо иметь:

Кg = ½ * m2/c2