области переполнения. Обычно не имеет смысла разбивать область переполнения на блоки, поскольку, как правило, возникает сравнительно немного переполнений; таким образом, "лишние" записи связываются одна с другой, поэтому {Ь+к)-я запись списка требует 1 + к обращений. Обычно стоит оставлять место для переполнений в каждом цилиндре дискового файла, чтобы как можно больше обращений оставалось в пределах одного и того же цилиндра.

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

а = N/Mb (54)

для фиксированного а и M,N оо. Любопытно, что при а = 1 асимптотическое количество обращений для неудачного поиска увеличивается с ростом Ь.

Таблица 2

СРЕДНЕЕ КОЛИЧЕСТВО ОБРАЩЕНИЙ В СЛУЧАЕ НЕУДАЧНОГО ПОИСКА ПО РАЗДЕЛЬНЫМ ЦЕПОЧКАМ

Таблица 3

СРЕДНЕЕ КОЛИЧЕСТВО ОБРАЩЕНИЙ В СЛУЧАЕ УСПЕШНОГО ПОИСКА ПО РАЗДЕЛЬНЫМ ЦЕПОЧКАМ

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

зовании этой схемы в каждом блоке содержится счетчик, указывающий количество пустых позиций записей. Такой блок удаляется из двусвязного списка только по достижении счетчиком нулевого значения. Для распределения переполнений может применяться "блуждающий указатель" (см. упр. 2.5-6) с тем, чтобы различные цепочки использовали различные блоки переполнения. Этот метод все еще не проанализирован, но может быть весьма полезен.

С) Использование открытой адресации. Можно обойтись и без ссылок и использовать "открытый" метод. При рассмотрении внешнего поиска линейное исследование, вероятно, лучше случайных проб, потому что величина с зачастую может быть выбрана таким образом, чтобы минимизировать скрытые задержки между последовательными доступами. Приближенная теоретическая модель линейного исследования, с которой мы работали ранее, может быть обобщена для учета влияния блоков. Она показывает, что линейное исследование в самом деле вполне удовлетворительно, пока таблица не слишком заполнена. Например, взгляните на табл. 4: при коэффициенте заполненности, равном 90%, и размере блока, равном 50, среднее количество обращений при успешно.м поиске равно всего лишь 1.04. Это даже лучше, чем требуемые при использовании метода цепочек (А) с тем же размером блока 1.08 обращения!

Таблица 4

СРЕДНЕЕ КОЛИЧЕСТВО ОБРАЩЕНИЙ В СЛУЧАЕ УСПЕШНОГО ПОИСКА ПРИ ЛИНЕЙНОМ ИССЛЕДОВАНИИ

Анализ методов А и С влечет очень интересные с математической точки зрения выводы; здесь мы приведем лишь некоторые результаты, поскольку подробности приводятся в упр. 49 и 55. Формулы содержат две функции, тесно связанные с (-функциями из теоремы К, а именно:

, \ " ng па ....

t") - + (п + 1)(п + 2) + {п + 1){п + 2){п + 3) +

((„1),+2(2)! +п + 3)! + )

{1-{1-а)Ща,п)). (56)

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

тахС;, = 1 + - = - + 1 + 0(6-1/2), (59)

тахС = 1+2(/г(6) + 1) +ух+0(6-1) (g

согласно приближению Стирлинга и анализу функции R{n) = R{l,n) - 1 (см. раздел 1.2.11.3).

Среднее количество обращений при успешном внешнем поиске с помощью линейного исследования имеет необыкновенно простой вид:

Слг W 1 -Ь tb{a) + t2bia) + *зь(а) + • • • (61)

Эту формулу можно пояснить следующим образом: общее среднее количество обращений при поиске всех N ключей равно NC, что представляет собой iV + Ti + Т2 + • • •, где Tk - среднее количество ключей, требующих более к обращений. Теорема Р гласит, что ключи можно вставлять в любом порядке без влияния на Cn, отсюда следует, что равно среднему числу переполняющих записей, которые имелись бы при использовании метода цепочек с М/к блоками размером кЬ, т. е. Nti.b{a), как и говорилось выше. Подробный анализ формулы (61) приводится в упр. 55.

Обсуждение практических вопросов построения внешних хеш-таблиц дано Чарльзом А. Ольсоном (Charles А. Olson) [Ргос. АСМ Nat. Conf. 24 (1969), 539-549]. В его работу включено несколько практических примеров; в ней указано, что количество переполняющих записей значительно увеличивается, если файл служит объектом частых вставок/удалений без перемещения записей. В работе также представлен анализ этой ситуации, выполненный совместно с Дж. А. деПейстером (J. А. dePeyster).

при M,N -> 00, а соответствующее число при успешном поиске может быть записано как

Предельные значения соответствуют величинам, приведенным в табл. 2 и 3.

Поскольку метод цепочек (А) требует отдельной области переполнения, необходимо оценить количество возможных переполнений. Среднее число переполнений составляет M{Cn - 1) = Ntb{a), так как С - 1 - среднее число переполнений в любом данно.м списке. Таким образом, табл. 2 может использоваться для нахождения требуемого размера области переполнения. Для фиксированного а стандартное отклонение общего количества переполнений будет примерно пропорционально VM при М 00.

Асимптотические значения С и См приведены в упр. 53, однако эти приближения не очень хороши при малых Ь или больших а. К счастью, ряд для R{a,n) сходится очень быстро даже при больших а, так что формулы могут быть вычислены с любой желательной точностью без больших трудностей. Максимальное значение достигается при а = 1, когда при 6 -> оо