ргосейте search(x: integer; а: ref; var h; boolean; var u: itemV begin if a = га/then

begin [x нет в дереве}

Присвоение значения х элементу и, установка h в true указывая, что элемент и передается вверх по дереву end else with а\ do

begin {поиск x на странице ct} ~~

двоичный поиск в массиве; if найдено then

увеличение счетчика появлений элемента else begin search {х, потомок, h, и)

if h then {передача вверх элемента и}

if (число элементов на ct) < 2п thea

включение и в страницу ct и установка h efalss else расщепление страницы и передача вверх среднего элемента

(4.83)

ница-корень содержит только один элемент. Детали можно посмотреть в программе 4.7.

На рис. 4.48 показан результат работы программы 4.7 при построении Б-дерева со следующей последовательностью вставляемых ключей:

20; 40 10 30 15; 35 7 26 18 22; 5; 42 13 46 27 8 32; 38 24 45 25;

Точки с запятой указывают моменты размещения новых страниц. Включение носледнего ключа вызывает два расщепления и размещение трех новых страниц.

Отметим особую роль в этой программе оператора присоединения with. Это видно уже в (4.83). В первую очередь оН означает, что внутри оператора, перед которым стоит соответствующий заголовок, идентификаторы компонент (полей) страницы автоматически относятся к странице а\. Ес-! реально страницы размещаются во внещней памяти, что, Р^ зумеется, необходимо в больших системах банков данных, оператор with дополнительно означает передачу указанн страницы в оперативную память. Поэтому каждое обраШ^н к search предполагает размещение в оперативной памя

.лой страницы, всего же необходимо самое большее k = lognN рекурсивных обращений. Следовательно, если де- Сро содержит N элементов, мы должны иметь возможность дзместить в оперативной памяти k страниц. Это накладывает

I 10 15 30 40 I

7 10 15 18 I 22 26 I I 35 40

I 5 7 I I 15 18 I I 22 26 I 35 40 lO 20 30 40

I 5 7 8 [ I 13 15 18] 22 26 27 ] [ 32 35

[117 8 ГТЗ 15 18 I 22 24 ) 26 27 32 35 38 11 42 45 461 ф Рис. 4.48. Рост Б-дерева порядка 2.

Граничение на размер страницы 2п. На самом деле нам Нужно иметь возможность разместить даже больше, чем

* страниц, так как включение может вызвать их расщепление. Естественно, что-корневую страницу лучше постоянно хранить

* оперативной памйти, йоскольку каждый поиск всегда начинается с корня.

Еще одно положительное качество Б-деревьев - это их Удобство и экономичность в случае чисто последовательного

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

Удаление элементов из Б-дерева очень просто в общи ц тах, но сложно з деталях. Мы можем выделить два разл ных случая:

1. Элемент, который нужно удалить, находится на страниц листе; тогда алгоритм удаления прост и очевиден.

2. Этот элемент не на странице-листе; тогда его нужно за нить на один или два лексикографически смежных эде мента, которые находятся на страницах-листьях и которые легко удалить.

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

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

Единственный выход - одолжить или отобрать элемент с одной из соседних страниц, а поскольку это требует вызова страницы Q в оперативную память - относительно дорогостоящей операции, - то мы попытаемся наилучшим образом воспользоваться этой нежелательной ситуацией и заберем сразу больше одного элемента. Обычно элементы Р и Q поровну распределяются на обе страницы. Это называется балансировкой.

Разумеется, может оказаться, что с Q нельзя забирать элементы, так как она тоже уже достигла своего минимального размера п. В этом случае общее число элементов на Р и Q равно 2п- 1, и мы можем слить эти две страницы в одну, добавив средний элемент со страницы-предка Р и Q; а затем можем полностью располагать страницей Q. Это - процесс, в точности - обратный расщеплению страниц. Его можно наблюдать, рассматривая удаление ключа 22 на рис. 447.

Удаление среднего ключа на странице-предке может вновь уменьшить ее размер ниже допустимой границы п, требуя тем самым дальнейших специальных мер (балансировки вли слияния) на более высоком уровне. В экстремальном случа^ слияние страниц может распространиться по всему пут' к корню. Если корень уменьшается до размера О, он уД ляется, что вызывает уменьшение высоты Б-дерева. Это едйй ственный случай, когда высота Б-дерева может уменьшитьс