CPSC 461: Copyright © 2002 Katrin Becker 1998-2002 Last Modified August 4, 2000 05:35 PM

B-Trees algorithms (pseudo-pascal: bold underlined = pass by reference; regular = pass by value)
The Structure

const max = 3 /* max # of keys = m-1

min = 1 /* min # of keys = ceiling(m/2) - 1

type page = record

RRN : integer
count : integer
key : array [1..max] of keytype
child : array [0..max] of pageptr

The Driver
AddKey (newkey: keytype; root: pageptr);

/* assume no duplicates */
variables promote : boolean

X : keytype
Xr : pageptr (ptr to ‘right’ subtree - the only one we need)
newpage : pageptr (temp)

begin

SEARCH (newkey, root, promote, X, Xr);
if promote then /* new root */

new (newpage) /* initialize */
with newpage do

RRN := newpage
count := 1
key := X
child[0] := root
child[1] := Xr

root := newpage

end

The Insertion
SEARCH (newkey: keytype; thispage: pageptr; promote: boolean; X: keytype; Xr: pageptr)
/* recursion terminates when we get to the end - past leaf - this is simpler - all insertions happen on the way back up */
var pos: 0..max
if thispage = nil then /* terminate recursion */

promote := true;
X := newkey;
Xr := nil;

else /* search current page */

/* use linear search for small trees but binary for large */
with thispage do

if newkey < key[1] then

pos := 0

else

pos := count
while (newkey < key[pos]) & (pos > 1) do

pos := pos - 1;

SEARCH (newkey, thispage.child[pos], promote, X, Xr);
if promote then

if count < max then

INSERT (X, Xr, thispage, pos)
promote := false;

else

SPLIT (X, Xr, thispage, pos, X, Xr)
promote := true;

end

end

endwith

endif

INSERT (X: keytype; Xr: pageptr; thispage: pageptr; K: position);
/* insert X and its pointer into thispage at position K; assumes node not full */
var i : position;
begin
with thispage do
for i := count downto K + 1 do
key[i + 1] := key[i]
child[i + 1] := child[i]
key[K + 1] := X;
child[K + 1] := Xr;
count := count + 1;
end

SPLIT ( X: keytype; Xr: pageptr; thispage: pageptr; K: position; Y: keytype; Yr: pageptr);
/* splits thispage with key X and pointer Xr at position K into thispage and Yr with median key Y */
var i, median : position;
begin

if K <= min then /* determine if new key goes in left or right half */

median := min

else

median := min + 1;

new(Yr); /* new node always goes on the right */
with thispage do

for i := median + 1 to max do /* move half the keys */

Yr^.key[i - median] := key[i];
Yr^.child[i - median] := child[i];

Yr^.count := max - median;
count := median;
if k <= min then

INSERT(X, Xr, thispage, K);

else

INSERT(X, Xr, Yr, K - median);

Y := key[count];
Yr^.child[0] := child[count]
count := count - 1;

end

end

Deletion:
MAINDELETE (target: keytype; root: pageptr);
/* delete target key from B-Tree with given root - calls recursive DELETE */
var found : boolean;
p : pageptr;
begin

DELETE ( target, root, found);
if not found then

ERROR /* can’t delete a key that isn’t there */

else if root^.count = 0 then /* deletion left root empty */

p := root;
root := root^.child[0]
free (p);

end

end

DELETE (target: keytype; thispage: pageptr; found: boolean);
var K : position;
begin

if thispage = nil then

found := false /* hitting an empty tree is an error */

else with thispage do

LOCATE (target, thispage, found, K); /* algorithm not included */
/* K is position of target in thispage */
if found then

if child[K - 1] = nil then /* thispage is a leaf */

REMOVE ( thispage, K);

else /* replace key[K] with its successor */

SUCESSOR ( thispage, K);
DELETE (key[K], child[K], found);
if not found then ERROR

endif

else /* target not found in current node - follow down */

DELETE (target, child[K], found);
if child[K] <> nil then /* return from recursive call */

if child[K]^.count < min then

RESTORE (thispage, K);

end

REMOVE (thispage: pageptr; K: position);
/* removes key[K] and child[K] from thispage */
var i : position
begin

with thispage do /* shift all keys left one and reduce count */

for i := K + 1 to count do

key[i - 1] := key[i];
child[i - 1] := child[i]
count := count - 1;

end

SUCCESSOR (thispage: pageptr; K: position);
/* replaces thispage^.key[K] by its immediate successor under natural order */
var Q : pageptr;
begin
Q := thispage^.child[K];
while Q^.child[0] <> nil do /* go left as far as possible */
Q := Q^.child[0];
thispage^.key[K] := Q^.key[1]
end

RESTORE ( thispage: pageptr; K: position );
/* restore child page to minimum number of keys */
/* finds a key to insert into child so as to restore minimum # of keys */
begin

if K = 0 then

if thispage^.child[1]^.count > min then /* case: leftmost key */

MOVELEFT ( thispage, 1);

else

COMBINE (thispage, 1);

else if K = thispage^.count then /* case: rightmost key */

if thispage^.child[K - 1]^.count > min then

MOVERIGHT (thispage, K);

else

COMBINE (thispage, K);

else /* remaining cases */

if thispage^.child[K - 1]^.count > min then

MOVERIGHT (thispage, K);

else if thispage^.child [K + 1]^.count > min then

MOVELEFT ( thispage, K + 1)

else

COMBINE ( thispage, K);

end;

MOVERIGHT ( thispage: pageptr; K: position );
var C: position;
begin

with thispage^.child[K]^ do begin

for C := count downto 1 do /* shift all keys in right node one position */

key[C + 1] := key[C]
child[C + 1] := child[C];

child[1] := child[0]; /* move key from parent into right node */
count := count + 1;
key[1] := thispage^.key[K]

end;
with thispage^.child [K - 1]^ do begin
/* move last key of left node into parent */

thispage^.key[K] := key[count]
thispage^.child[K]^.child[0] := child[count];
count := count - 1;

end;

end;

MOVELEFT ( thispage: pageptr; K: position );
var C: position;
begin

with thispage^.child[K - 1]^ do /* move key from parent into left node */

count := count + 1;
key[count] := thispage^.key[K];
child[count] := thispage^.child[K]^.child[0]

end;
with thispage^.child [K]^ do begin /* move key from right node into parent */

thispage^.key[K] := key[1];
child[0] := child[1];
count := count - 1;
for C := 1 to count do begin

/* shift all keys in right node one position left */
key[C] := key[C + 1]
child[C] := child[C + 1]

end;

end;

end;

COMBINE ( thispage; K: position ); /* combine adjacent nodes below thispage*/
var C : position;
Q : pageptr; /* points to right node which will be emptied and deleted */
begin

Q := thispage^.child[K];
with thispage^.child [K - 1]^ do begin /* work with left node */

count := count + 1;
key [count] := thispage^.key[K]; /* insert key from parent */
child [count] := Q^.child [0];
for C := 1 to Q^.count do begin

count := count + 1;
key [count] := Q^.key[C];
child [count] := Q^.child[C];

endfor;
with thispage^ do begin
/* delete key from parent node */
for C := K to count - 1 do

key[C] := key[C + 1];
child[C] := child[C + 1];

count := count - 1;

endwith;
free ( Q ); /* dispose of empty right node */

end;

CPSC 461: Copyright © 2002 Katrin Becker 1998-2002 Last Modified August 4, 2000 05:35 PM