СД типа индексно-последовательный файл

0 147

 
адрес ключ
адрес ключ
Данная структура является реализацией следующей идеи: вычисляется приблизительное место, где может находиться искомая запись файла, а затем последовательно просматривается файл до конца, начиная с найденного места, пока элемент не будет найден.
105 60
106 70
107 81
108 83
ключ указатель
                                                    Блок 2
     
Отображение идет в отношении n:1 (множество ключей отображается на 1 блок).
 
Упорядоченный файл делится на блоки. Блок содержит определенное число записей (обычно одинаковое количество). На каждый блок в справочнике заводится одна статья, состоящая из указателя и ключа. Каждая статья содержит адрес первой записи, а поле ключа – значение последней записи. Поиск записи с нужным значением осуществляется в два этапа:
1) Просматривается справочник и определяется блок, к которому должна принадлежать искомая запись (при этом последовательно просматривается индекс-таблица, пока не будет найден первый ключ, не превышающий заданный). Т.к. справочник упорядочен, то можно использовать ускоренные методы поиска.
2) На втором этапе производится обращение к найденному блоку, где осуществляется последовательный поиск нужной записи (линейный или бинарный). Если известно, что количество записей N, то t(N) ~ (N/n + n) = 0, где n – искомое количество записей. – N/n2 + 1 = 0 Þ n =.
При включении элемента блок может быть уже заполнен, тогда используется файл переполнения. В этом случае при поиске мы просматриваем и файл переполнения. При удалении и при записи меняется значение ключа, т.е. происходит корректировка справочника относительно последнего элемента.
Таким образом, поиск в файле основывается на использовании индекса и последовательном просмотре в нем и в отдельных частях файла, поэтому такой файл называется индесно-последовательным
Если элементов в файле много, то индекс-таблица также оказывается большой размерности. В этом случае создается индекс-таблица второго уровня для ускорения поиска в таблице первого уровня, т.е. в этом случае индекс-таблица первого уровня рассматривается как последовательный файл.
 
Например, количество записей в файле равно приблизительно 1 млн.
Число уровней
Размер блока
Занимаемая справочником
Среднее число обращений

Смотрите также  Отдел I. Судебная организация

500000 (n/2)

 

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

Войти с помощью: 
Подписаться
Уведомление о
guest
0 Комментарий
Встроенные отзывы
Посмотреть все комментарии
0
Будем рады вашим мыслям, пожалуйста, прокомментируйте.x
()
x