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

адрес ключ

адрес ключ

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

105 60 106 70 107 81 108 83

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

			Блок 2

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

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

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

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

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

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

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

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

Число уровней	Размер блока	Занимаемая справочником память	Среднее число обращений
			500000 (n/2)

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

Дата добавления: 2014-01-07