Ца рис. 4.49 показан постепенный распад Б-дерева р0С. 4.48 при последовательном удалении ключей:

25 45 24; 38 32; 8 27 46 13 42; 5 22 18 26; Р 7 35 15;

очки с запятой снова указывают места скачков , т. е. осво-вЖДения страниц. Алгоритм удаления включен в программу

[5 7 8 I [l3151820 26 27 [[ЗБ404246

(d) [1022 I

5 7 I 151820 26 30 35401

(е) 115

7 10 I [20303540

(f) [10 20 3040

Щ Рис. 4.49. Распад Б-дерева порядка 2.

- Особенно примечательно его сходство с алгоритмом уда- Ния из сбалансированного дерева. Исчерпывающий анализ свойств Б-деревьев выполнен статье Бэйера и Мак-Крейта [4.2]. В частности, в ней рас-

program Btree{input,oufput);

[поиск, включение и удаление в Б-дереве)

const и = 2; пи = 4; [размер страницы] .

type ref \page;

item = record key: integer; P- ref;

count: integer;

end ;

page = record m: 0. .nn; [число элементов] pO: ref;

e: array [1.. nn] of item; end ;

yat root, q: ref; x: integer;

h: boolean: u: item;

procedure search(x: integer; a: ref; var h: boolean; var V: item); [ Поиск ключа x в Б-дереве с корнем а; если найден, увеличение счетчика, иначе включение в дерево элемента с ключом х и счетчиком 1. Если элемент должен передаваться на низший уровень, присвоить его v; h:- depeeo стало выше ] var k,l,r: integer; q: ref; и: item; procedure insert;

var i: integer; b: ref; begin [включение и справа от аТ. е[г]] with at do begin if m < nn then

begin m := h := false;

for i := m downto r+2 do ф'] := e[i-1]; e[r+\] := и end else

begin [страница at заполнена; расщепить ее и присвоШ№ полученный элемент v] nevAp);

if г < п then

begin if г = и then v : и else begin V :- e[n];

for / := n downto r+2 do := III

e[r+l] := w end ;

for I := 1 to и do 6.ф] := a\.i+n] end else

begin [включение и в первую страницу] г := г-п; V := е[п-\-\]: for / := 1 to r-l do fct4l := a\.e[i+n+lV>

for i := r+1 to и do Ь|-*И оТ-ф'+и] end ;

end [with] end {torn} J jegin [поиск ключа x на странице t; h-false] if e = nil then

.jbegin {элемента с ключом X нет в дереве] h : з - в;

fwith V do begin ЛгЗ' х; count := 1; j? :=< nil end cod else with flf do

/ :== 1; r := /и; [двоичный поиск в массиве] repeat :== (/+/) div 2;

if л: < ф\ .fceythen г 5= A:-1; if л > с[/с] .A:e> then / A;+l; antil r <l; if /-Г > 1 then

begin [найдено] e[k] .count :== k] .count + 1; A 1= false end else

begin [элемента нет на этой странице] if г ~ 6 then q := />0 else q := с[г] . pj search(x,q,h,u); if Л then wjre/*

end end