JOHN

PETER

ALBERT

MARY

ROBERT

CAROL

PAUL

CHRIS

TINA

GEORGE

PAMELA

Рнс, 4,43. Сильно ветвящееся дерево.

/щ0Й интерес. Это - формирование и использование крупно- ч^-табных деревьев поиска, в которых необходимы и вклю-

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

Рис. 4.44. Бинарное дерево, разделенное на страницы .

памяти. Если множество данных, состоящее, например, из миллиона элементов, хранится в виде бинарного дерева, то для поиска элемента потребуется в среднем около log210® 20 шагов поиска. Поскольку теперь каждый шаг включает обращение к диску (с собственным латентным временем), будет весьма желательна организация памяти, требующая меньше обращений. Сильно ветвящееся дерево является идеальным решением этой проблемы. Если происходит обращение к некоторому одиночному элементу, расположенному на внешнем устройстве, то без больших дополнительных затрат можно обращаться также к целой группе элементов. Отсюда следует, ТО дерево нужно разделить на поддеревья, считая, что все ти поддеревья одновременно полностью доступны. Мы будем называть такие поддеревья страницами. На рис. 4.44 показано йнарное дерево, разделенное на страницы, состоящие из узлов каждая.

Уменьшение количества обращений к диску - а теперь бращение к каждой странице предполагает обращение диску - может быть значительным. Предположим, что мы Р*1Цили помещать на странице 100 узлов (это разумная ХФр^). тогда дерево поиска, содержащее миллион элементов.

потребует в среднем только logioo 10 = 3 обращений к гт ницам вместо 20. Но конечно, если дерево растет случайн^ образом , то наихудший случай может потребовать W обращений! Понятно, что в случае сильно ветвящихся ревьев почти обязательна схема управления их ростом.

4J.1. Б-деревья

При поиске критерия управляемого роста нужно сряГ отвергнуть идеальную сбалансированность, так как она тр/ бует слишком больших затрат на балансировку. Очевидно что правила необходимо несколько смягчить. Очень разумный критерий был сформулирован Р. Бэйером [4.2]: каждая стра-ница (кроме одной) содержит от п до 2п узлов при заданном постоянном п,-Следовательно, в дереве с N элементами к максимальным размером страницы 2п узлов наихудший слу-чай потребует \ognN обращений к страницам, а обращения к страницам составляют, как известно, основную часть затрат на поиск. Кроме того, важный коэффициент использования памяти составляет не менее 50%, так как страницы заполнены хотя бы наполовину. При всех этих преимуществах данная схема требует сравнительно простых алгоритмов поиска, включения и удаления. В дальнейшем мы подробно их изучим.

Рассматриваемые структуры данных называются Б-де-ревьями и имеют следующие свойства (п называется порядком Б-дерева):

1. Каждая страница содержит не более 2п элементов (ключей).

2. Каждая страница, кроме корневой, содержит не менее я элементов.

3. Каждая страница является либо листом, т. е. не имеет потомков, либо имеет т -f- 1 потомков, где т - число находящихся на ней ключей.

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

На рис. 4.45 показано Б-дерево порядка 2 с 3 уровням -Все страницы содержат 2, 3 или 4 элемента. Исключением является корень, которому разрешается содержать только один элемент. Все листья находятся на уровне 3. Ключи раС положены в возрастающем порядке слева направо, если спро ектировать дерево на один уровень, вставляя потомков мсЖДУ ключами, находящимися на странице-предке. Такое располО' жение представляет естественное развитие принципа органй зации бинарных деревьев поиска и определяет метод поиск* элемента с заданным ключом. Рассмотрим страницу, nMSi щую вид, как показано на рис. 4.46, и пусть задан аргумеЯ