Appendix B. Pseudo-code for Inserting an Entry in a B+-tree Algorithm 1: insert(key K, pointer P) 1 if tree is empty then 2 Create an empty leaf node L 3 insert in leaf(L, K, P) 4 Register node L as the new root 5 else 6 Find the leaf node L that should contain key K 7 if L has less than n − 1 keys then 8 insert in leaf(L, K, P) 9 else 10 Copy L.P0 · · ·L.Kn−2 to a block of memory T that can hold n (pointer, key) pairs 11 insert in leaf(T, K, P) 12 Create node L 0 13 Set L 0 .Pn−1 = L.Pn−1 14 Erase L.P0 through L.Kn−2 from L 15 Copy T.P0 through T.Kdn/2e−1 from T into L starting at L.P0 16 Copy T.Pdn/2e through T.Kn−1 from T into L 0 starting at L 0 .P0 17 Set L.Pn−1 = L 0 18 Let K0 be the smallest key in L 0 19 insert in parent(L, K0 , L 0 ) Algorithm 2: insert in leaf(node L, key K, pointer P) 1 if K < L.K0 then 2 Insert P, K into L just before L.P0 3 else 4 Let Ki be the highest key in L that is less than K 5 Insert P, K into L just after T.Ki 3 Algorithm 3: insert in parent(node N, key K, node N0 ) 1 if N is the root of the tree then 2 Create a new node R containing N, K, N0 3 Register node R as the new root of the tree 4 return 5 Let P = parent(N) 6 if P has less than n pointers then 7 Insert(K, N0 ) in P just after N 8 else 9 Copy P to a block of memory T that can hold P and (K, N0 ) 10 Insert (K, N0 ) into T just after N 11 Erase all entries from P 12 Create node P 0 13 Copy T.P0 · · · T.Pd(n+1)/2e−1 into P 14 Copy T.Pd(n+1)/2e · · · T.Pn into P 0 15 Let K0 = T.Kd(n+1)/2e−1 16 insert in parent(P, K0 , P 0 ) Appendix C. Pseudo-code for Deleting an Entry in a B+-tree Algorithm 4: delete(key K) 1 find the leaf node L that contains K 2 delete entry(L, K) 4 Algorithm 5: delete entry(node N, key K) 1 delete K and the corresponding pointer from N 2 if N is the root then 3 if N has only one remaining child then 4 Register the child of N as the new root of the tree 5 else if N has too few keys/pointers then 6 Let N0 be the previous or next child of parent(N) 7 Let K0 be the key between pointers N and N0 in parent(N) 8 if entries in N and N0 can fit in a single node then 9 if N0 is the predecessor of N then 10 merge(N0 , K0 , N) 11 else 12 merge(N, K0 , N0 ) 13 else 14 // redistribution: move a key and a pointer from node N0 to node N 15 if N0 is the predecessor of N then 16 if N is a non-leaf node then 17 Let m be such that N0 .Pm is the last pointer in N0 18 Insert (N0 .Pm, K0 ) as the first pointer and key in N by shifting other pointers and keys right 19 Remove (N0 .Km−1, N0 .Pm) from N0 20 Replace K0 in parent(N) by N0 .Km−1 21 else 22 Let m be such that (N0 .Pm, N0 .Km) is the last pointer/key pair in N0 23 Insert (N0 .Pm, N0 .Km) as the first pointer and key in N by shifting other pointers and keys right 24 Remove (N0 .Pm, N0 .Km) from N0 25 Replace K0 in parent(N) by N0 .Km 26 else 27 . . . symmetric to the then case . . . Algorithm 6: merge(node N0 , key K0 , node N) 1 if N is not a leaf node then 2 Append K0 and all pointers and keys in N to N0 3 else 4 Append all (Ki , Pi) pairs in N to N0 5 Set N0 .Pn−1 = N.Pn−1 6 delete entry(parent(N), K0 ) Appendix D. Execution Log When you complete this assignment, your program will produce the following output: input.txt % insert c 1 @0(1, c, null, null, null) % insert d 2 5 @0(1, c, 2, d, null) % insert f 3 @0(@1, f, @2, null, null) @1(1, c, 2, d, @2) @2(3, f, null, null, null) % insert a 5 @0(@1, d, @2, f, @3) @1(5, a, 1, c, @2) @2(2, d, null, null, @3) @3(3, f, null, null, null) % insert b 6 @0(@1, d, @2, null, null) @1(@3, c, @4, null, null) @3(5, a, 6, b, @4) @4(1, c, null, null, @5) @2(@5, f, @6, null, null) @5(2, d, null, null, @6) @6(3, f, null, null, null) % insert b 7 InvalidInsertionException @0(@1, d, @2, null, null) @1(@3, c, @4, null, null) @3(5, a, 6, b, @4) @4(1, c, null, null, @5) @2(@5, f, @6, null, null) @5(2, d, null, null, @6) @6(3, f, null, null, null) % delete d @0(@1, c, @2, d, @3) @1(5, a, 6, b, @2) @2(1, c, null, null, @3) @3(3, f, null, null, null) % delete c @0(@1, d, @2, null, null) @1(5, a, 6, b, @2) @2(3, f, null, null, null) % delete c InvalidDeletionException @0(@1, d, @2, null, null) @1(5, a, 6, b, @2) @2(3, f, null, null, null) % delete f @0(5, a, 6, b, null)