Внешний поиск a

Рис. 16.2. Структура индексно-последовательного файла
В последовательном индексе ключи хранятся упорядоченными в полных страницах (справа), а индекс указывает на наименьший ключ в каждой странице (слева). При добавлении ключа требуется перестроить всю структуру данных.


Рис. 16.3. Примеры размеров наборов данных
Эти впечатляющие граничные значения позволяют смело принять, что на практике вряд ли встретится таблица символов, содержащая более 1030 элементов. Даже в такой неимоверно большой базе данных при 1000-путевом ветвлении элемент с заданным ключом можно найти с помощью менее 10 проб. И даже если бы как-то удалось записать информацию о каждом электроне во Вселенной, 1000-путевое ветвление позволило бы получить доступ к любому конкретному элементу с помощью менее 27 проб.
Мы не будем рассматривать реализации поиска и построения индексов подобного типа, поскольку они представляют собой специальные случаи более общих механизмов, рассматриваемых в следующем разделе (см. упражнение 16.17 и программу 16.2).
Упражнения
16.1. Составьте таблицу значений logM N для M= 10, 100 и 1000 и N= 10³, 10⁴, 10⁵ и 10⁶ .
16.2. Нарисуйте структуру индексно-последовательного файла для ключей 516, 177, 143, 632, 572, 161, 774, 470, 411, 706, 461, 612, 761, 474, 774, 635, 343, 461, 351, 4 30, 664, 127, 34 5, 171 и 357 при M= 5 и N= 6.
16.3. Предположим, что мы строим структуру индексно-последовательного файла для N элементов, со страницами емкостью M, но оставляем на каждой странице к свободных мест для возможного расширения. Приведите формулу для определения количества проб, необходимых для выполнения поиска, в виде функции от N, M и к. Используйте эту формулу для определения количества проб, необходимых для выполнения поиска при k = M/10, M= 10, 100 и 1000 и N= 10³, 10⁴, 10⁵ и 10⁶ .
16.4. Предположим, что затраты на одну пробу равны приблизительно а единиц времени, а средние затраты на поиск элемента на странице составляют приблизительно PM единиц времени. Найдите значение M, при котором затраты на поиск в структуре индексно-последовательного файла минимальны, при   и N= 10³, 10⁴, 10⁵ и 10⁶ .