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

Д

адрес ключ

адрес ключ

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

ключ указатель

105. 60

106. 70

107. 81

108. 83

53 100

83 105

. .

. .

Блок 1

Блок 2

.

.

Блок n

100 25

101. 30

102. 40

103. 51

104. 53

. .

Блок 1

Блок 2

Отображение идет в отношении n:1 (множество ключей отображается на 1 блок).

Упорядоченный файл делится на блоки. Блок содержит определенное число записей (обычно одинаковое количество). На каждый блок в справочнике заводится одна статья, состоящая из указателя и ключа. Каждая статья содержит адрес первой записи, а поле ключа – значение последней записи. Поиск записи с нужным значением осуществляется в два этапа:

1. Просматривается справочник и определяется блок, к которому должна принадлежать искомая запись (при этом последовательно просматривается индекс-таблица, пока не будет найден первый ключ, не превышающий заданный). Т.к. справочник упорядочен, то можно использовать ускоренные методы поиска.

2. На втором этапе производится обращение к найденному блоку, где осуществляется последовательный поиск нужной записи (линейный или бинарный). Если известно, что количество записей N, то t(N) ~ (N/n + n) = 0, где n – искомое количество записей. – N/n² + 1 = 0  n = .

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

Таким образом, поиск в файле основывается на использовании индекса и последовательном просмотре в нем и в отдельных частях файла, поэтому такой файл называется индесно-последовательным

Если элементов в файле много, то индекс-таблица также оказывается большой размерности. В этом случае создается индекс-таблица второго уровня для ускорения поиска в таблице первого уровня, т.е. в этом случае индекс-таблица первого уровня рассматривается как последовательный файл.

Например, количество записей в файле равно приблизительно 1 млн.

Число уровней	Размер блока	Занимаемая справочником память	Среднее число обращений
0	0	0	500000 (n/2)
1		1000	1000
2		10000	150
3		33000	63
4		66000	40
5		100000	30

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