Past exam question: 2072 Ashwin (Regular), Q9
Open in the Padhaiko appQuestion
Construct B-tree of order 5 for the set of data C N G A H E K Q M F W L T Z D P R X Y S showing each steps.
Solution
Order-5 B-Tree Rules (, Max 4 Keys/Node) and First Split (C, N, G, A, H): Using alphabetical order (A < B < ... < Z):
- Insert
C, N, G, A: leaf[A, C, G, N](full). - Insert
H:[A, C, G, H, N]overflows promote medianGto root:
[G]
/ \
[A, C] [H, N]Insert E, K, Q, M, F, W, L, T:
- Insert
E:[A, C, E]. - Insert
K, Q: right leaf[H, K, N, Q](full). - Insert
M:[H, K, M, N, Q]overflows promoteMto root[G, M]; leaves:[A, C, E],[H, K],[N, Q]. - Insert
F:[A, C, E, F](full). - Insert
W:[N, Q, W]. - Insert
L:[H, K, L]. - Insert
T:[N, Q, T, W](full).
Insert Z, D, P, R, X, Y, S (Splits and Root Growth):
- Insert
Z:[N, Q, T, W, Z]overflows promoteTto root[G, M, T]; rightmost leaves:[N, Q],[W, Z]. - Insert
D:[A, C, D, E, F]overflows promoteDto root[D, G, M, T](root now full!); leaves:[A, C],[E, F],[H, K, L],[N, Q],[W, Z]. - Insert
P, R: leaf[N, P, Q, R](full). - Insert
X, Y: leaf[W, X, Y, Z](full). - Insert
S: leaf[N, P, Q, R, S]overflows promoteQinto full root[D, G, M, Q, T]! Root overflows and splits around medianMinto a new root[M]:
[M]
/ \
[D, G] [Q, T]
/ | \ / | \
[A,C] [E,F] [H,K,L] [N,P] [R,S] [W,X,Y,Z]Answer:
Final order-5 B-tree:
- Root:
[M] - Level 1:
[D, G]and[Q, T] - Leaves:
[A, C],[E, F],[H, K, L](under[D, G]);[N, P],[R, S],[W, X, Y, Z](under[Q, T]).