Adapt Algorithms 17.2 and 17.3, which outline search and insertion procedures for a B⁺-tree, to a B-tree.

Algorithm 17.2. Searching for a Record with Search Key Field Value K, Using a B⁺-Tree
n ← block containing root node of B⁺-tree;
read block n;
while (n is not a leaf node of the B⁺-tree) do
begin
q ← number of tree pointers in node n;
if K ≤ n.K₁ (*n.K_i refers to the ith search field value in node n*)
then n ← n.P₁ (*n.P_i refers to the ith tree pointer in node n*)
else if K > n.K_q−1
then n ← n.P_q

else begin
search node n for an entry i such that n.K_i−1 < K ≤n.K_i;
n ← n.P_i
end;
read block n
end;
search block n for entry (K_i, Pr_i) with K = K_i; (* search leaf node *)
if found 

Algorithm 17.3. Inserting a Record with Search Key Field Value K in a
B⁺-Tree of Order p
n ← block containing root node of B⁺-tree;
read block n; set stack S to empty;
while (n is not a leaf node of the B⁺-tree) do
begin
push address of n on stack S;
(*stack S holds parent nodes that are needed in case of split*)
q ← number of tree pointers in node n;
if K ≤n.K₁ (*n.K_i refers to the ith search field value in node n*)
then n ← n.P₁ (*n.P_i refers to the ith tree pointer in node n*)
else if K ← n.K_q−1
then n ← n.P_q
else begin
search node n for an entry i such that n.K_i−1 < K ≤n.K_i;
n ← n.P_i
end;
read block n
end;
search block n for entry (K_i,Pr_i) with K = K_i; (*search leaf node n*)
if found
then record already in file; cannot insert
else (*insert entry in B⁺-tree to point to record*)
begin
create entry (K, Pr) where Pr points to the new record;
if leaf node n is not full
then insert entry (K, Pr) in correct position in leaf node n
else begin (*leaf node n is full with pleaf record pointers; is split*)
copy n to temp (*temp is an oversize leaf node to hold extra entries*);
insert entry (K, Pr) in temp in correct position;
(*temp now holds p_leaf + 1 entries of the form (K_i, Pr_i)*)
new ← a new empty leaf node for the tree; new.Pnext ← n.P_next ;
j ← ⎡(p_leaf + 1)/2 ⎤ ;
n ← first j entries in temp (up to entry (K_j, Pr_j)); n.P_next ← new;

new ← remaining entries in temp; K ← K_j ;
(* now we must move (K, new) and insert in parent internal node;
however, if parent is full, split may propagate*)
finished ← false;
repeat
if stack S is empty
then (←no parent node; new root node is created for the tree*)
begin
root ← a new empty internal node for the tree;
root ← ; finished ← true;
end
else begin
n ← pop stack S;
if internal node n is not full
then
begin (*parent node not full; no split*)
insert (K, new) in correct position in internal node n;
finished ← true
end
else begin (* internal node n is full with p tree pointers;
overflow condition; node is split*)
copy n to temp (*temp is an oversize internal node*);
insert (K, new) in temp in correct position;
(*temp now has p + 1 tree pointers*)
new ← a new empty internal node for the tree;
j ← ⎣((p + 1)/2⎦ ;
n ← entries up to tree pointer Pj in temp;
(*n contains 1, K₁, P₂, K₂, … , Pj₋₁, K_j−1, P_j >*)
new ← entries from tree pointer P_j+1 in temp;
(*new contains < P_j+1, K_j+1, … , K_p−1, P_p, K_p, P_p+1 >*)
K ← K_j
(* now we must move (K, new) and insert in
parentinternal node*)
end
end
until finished
end;
end