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

Некоторые вычисления, проведенные С. П. Гошем (S. Р. Ghosh) и М. Э. Сенко (М. Е. Senko) [JACM 16 (1969), 569-579], приводят к мысли о том, что неплохо иметь большие листья длиной, скажем, до 10 последовательных страниц. При помощи линейной интерполяции в известном для каждого листа диапазоне ключей можно предположить, в какой из десяти страниц должен находиться данный аргумент. Если такая догадка окажется неверной, будет потеряно время, однако эксперименты свидетельствуют о том, что эти потери могут оказаться меньшими, чем время, сэкономленное на уменьшении дерева.

Т. X. Мартин (Т. Н. Martin) [неопубликовано] указал, что идея, лежащая в основе В-деревьев, также может использоваться для ключей переменной длины. Нет необходимости требовать, чтобы количество потомков каждого узла находилось в пределах [т/2 .. т]; вместо этого можно просто сказать, что каждый узел должен быть заполнен данными как минимум наполовину. Механизм вставки и разделения продолжает неплохо работать, хотя точное количество ключей в узле зависит от их длин. Однако ключи не должны быть очень длинными, иначе это может все испортить (см. упр. 5).

Другой важной модификацией схемы В-дерева является идея переливания, предложенная Байером (Bayer) и Мак-Крейтом (McCreight). Она заключается в улучшении алгоритма вставки путем сопротивления соблазну частого разделения. Вместо этого предлагается использовать локальные повороты. Предположим, что имеется переполненный узел, содержащий m ключей и m -f 1 указатель. Вместо его разделения можно сначала обратить внимание на соседний узел справа, у которого, к примеру, есть j ключей и j -- 1 указатель. В родительском узле имеется ключ Kf, который разделяет ключи двух соседей. Схематично это можно изобразить так:

"0

При j < m - 1 можно избежать разделения с помощью простой перегруппировки: оставляем (т -I- j)/2j ключей в левом узле, заменяем в родительском узле Kf на 7(Г(т+)/2Л-1 и помещаем "(т -I-j)/2] оставшихся ключей (в том числе Kf) и соответствующие указатели в правый узел. Таким образом, заполненный узел "переливается" в соседний. С другой стороны, если соседний узел также заполнен (j = m - 1), можно разделить оба узла, сделав из них три узла, заполненных на две трети и содержащих соответственно [(2т - 2)/3 ключей:

(2т - l)/3j и [2m/3j

(10)

Если у исходного узла нет соседа справа, можно обратиться с предложением о переливании к соседу слева (если имеются оба соседа, то избегать разделения узла можно до тех пор, пока они оба не заполнятся). И, наконец, если исходный узел не имеет соседей, значит, это корневой узел. Можно изменить определение В-дерева, позволив корню содержать до 2 [(2т - 2)/3j ключей, чтобы при разделении корень давал два узла, содержащих по [(2т - 2)/3j ключей. (Не рассмотренный автором случай переливания к соседу, родительский узел которого является соседом родителя исходного узла, хотя и возможен теоретически, но слишком сложен, чтобы иметь преимущество перед разделением узлов. - Прим. перев.)

В результате применения всех описанных технологий выводится новая "порода" деревьев (назовем их В*-деревьями порядка т), которые можно определить следующим образом. .1) Каждый узел, за исключением корневого, имеет не более m потомков.

ii) Каждый узел, за исключением корневого и листьев, имеет не менее (2т - 1)/3 потомков.

iii) Корневой узел имеет не менее 2 и не более 2 [(2т - 2)/3j -Н 1 потомков.

iv) Все листья находятся на одном уровне.

v) Узлы, не являющиеся листьями и имеющие к потомков, содержат А; - 1 ключ.

Важным изменением является условие (ii), которое утверждает, что используется минимум две трети имеющегося в каждом узле пространства. Это изменение позволяет не только более эффективно использовать пространство, но и повысить скорость работы, поскольку при этом в формулах (6) и (7) [т/2] заменяется на [(2т - 1)/3 . Однако процесс вставки становится более медленным, так как узлам приходится уделять больше внимания при их заполнении (см. приближенный анализ в работе В. Zhang and М. Hsu, Acta Informatica 26 (1989), 421-438).

Иногда выгоднее позволить узлам быть заполненными менее чем наполовину, чем часто их изменять. Такая ситуация была проанализирована в работе Т. Johnson and D. Shasha, J. Comput. Syst. Sci. 47 (1993), 45-76.

Возможно, читатель скептично настроен по отношению к В-деревьям, поскольку степень ветвления в корне может быть равна 2. Какой смысл тратить обращение к диску для разветвления всего лишь на 2 пути?! Однако простейшая схема буферизации, называемая замещением дольше всего не используемой страницы, позволяет преодолеть это неудобство. Можно выделить во внутренней памяти несколько буферов и избежать реального ввода с диска при наличии страницы в памяти. При использовании этой схемы алгоритмы поиска или вставки выполняют команды "виртуального чтения", которые транслируются в реальные команды ввода данных с диска только при отсутствии необходимой страницы в памяти. Последующая команда "освобождения" вьшолняется в том случае, когда информация в буфере модифицируется алгоритмом. Когда требуется действительное чтение, выбирается

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

Поскольку число уровней дерева обычно мало по сравнению с количеством буферов, такая страничная схема обеспечивает постоянное наличие корневой страницы в памяти; если корень имеет 2-3 потомка, то же самое можно сказать и о страницах первого уровня. Заметим, что страницы, которые могут понадобиться для разделения при вставке, автоматически присутствуют в памяти в силу обращения к ним во время предыдущего поиска.

Эксперименты Э. Мак-Крейта (Е. McCreight) показали, что такая политика работы вполне успешна. Например, им было найдено, что при 10 буферах и m = 121 процесс вставки 100 ООО ключей в порядке возрастания требует только 22 действительных чтений и только 857 реальных команд записи. Таким образом, большая часть действий выполнялась во внутренней памяти. Далее, полученное дерево содержало всего 835 узлов, лишь на один узел больше, чем минимально возможное значение [l00000/(m - 1)] = 834; следовательно, память была использована практически на 100%. В этом эксперименте применялась технология переливания, но с разделением на две части согласно (4), а не на три, как в (10) (см. упр. 3).

В другом эксперименте, также с десятью буферами, m = 121 и использованной технологией переливания, Э. Мак-Крейт вставил 5 000 ключей в первоначально пустое дерево в случайном порядке. При этом было получено двухуровневое дерево с 48 узлами (утилизация памяти составила 87%) после вьшолнения 2 762 реальных чтений и 2 739 реальных записей. Затем для 1 ООО случайных поисков потребовалось 786 реальных чтений. В результате того же эксперимента без применения переливания было построено двухуровневое дерево с 62 узлами (утилизация памяти - 67%) после вьшолнения 2 743 реальных чтений и 2800 реальных записей. Далее для 1 ООО случайных поисков потребовалось 836 реальных чтений. Это показывает не только эффективность страничной схемы, но и преимущества, полученные от использования технологии переливания.

Эндрю Яо (Andrew Yao) доказал, что среднее количество узлов после случайных вставок без переливания для больших N vl т равно

iV/(m \п2)+ 0{Nlm),

так что утилизация памяти будет составлять примерно In 2 = 69.3% [Acta Informatica 9 (1978), 159-170]. Более детальный анализ можно найти в работах В. Eisenbarth, N. Ziviani, G. Н. Gonnet, К. Mehlhorn, and D. Wood, Information and Control 55 (1982), 125-174; R. A. Baeza-Yates, Acta Informatica 26 (1989), 439-471.

В-деревья со времен своего изобретения стали чрезвычайно популярны. Обратитесь, например, к статье Дугласа Комера (Douglas Comer) в Computing Surveys 11 (1979), 121-138, 412, в которой обсуждаются ранние разработки и описывается широко используемая система VSAM (Virtual Storage Access Method - метод доступа к виртуальной памяти), созданная в IBM Corporation. Одним из новшеств VSAM была репликация блоков дисковых цилиндров с целью минимизации времени обращения.

Две из наиболее интересных разработок основ стратегии В-деревьев получили одинаковые имена: "5В-деревья" и "SB-деревья! 5В-дерево П. Ю. ОНейла