Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
98-Comp-B3, Data Bases & File Systems — National Exams, May 2015. 3 hours, closed book (calculators permitted). Candidates were instructed to answer five questions: one of Questions 1/2, one of Questions 3/4, and three of Questions 5–8 — only those five are marked. All 8 questions are answered below for completeness (this is a study resource covering the full syllabus).
Reference texts: Silberschatz, Korth & Sudarshan, Database System Concepts (7th ed.) — ER modelling, normal forms, and transactions/serializability; Ramakrishnan & Gehrke, Database Management Systems (3rd ed.) — B+-tree indexing, SQL, and relational algebra.
Given. An order-4 B+-tree (4 pointers fit in a node, so each node holds at most 3 keys; a non-root node must hold at least ⌈3/2⌉=2 keys if it is a leaf, or at least ⌈4/2⌉=2 pointers if it is internal). The 11 keys 2, 5, 8, 10, 15, 18, 23, 25, 28, 31, 33 are inserted one at a time, in ascending order, into an initially empty tree.
Find. (a) The tree's shape once all 11 keys have been inserted. (b) The tree after each of insert 24, delete 2, insert 35, applied in turn to the result of (a).
Approach. Standard B+-tree maintenance (Silberschatz & Ramakrishnan-Gehrke algorithm): on insert, descend to the correct leaf and add the key in sorted position; if a leaf now holds 4 keys it splits into two leaves of 2 and 2, and the smallest key of the new right leaf is copied up to the parent (data always stays in the leaves); if an internal node is pushed to 4 keys it splits too, but its median key moves up (it is not duplicated, since internal keys are pure routing separators). On delete, remove the key from its leaf; if the leaf drops below the minimum fill, first try to borrow a key from an adjacent sibling through the parent, and only merge the two nodes (dropping a separator from the parent) when neither sibling has a key to spare — an internal-node underflow after a merge is fixed the same way, one level up.
Part (a) — building the tree. Tracing all 11 insertions in order (verified against a Python implementation of the algorithm):
Insert 2, 5, 8. Single leaf [2,5,8] — 3 keys, at capacity but not overflowing.
Insert 10. Leaf would hold [2,5,8,10] (4 keys) — overflow. Split into [2,5] and [8,10]; copy up 8. Root: [8].
Insert 15, 18. Both keys are ≥ 8, so both route to the right leaf [8,10]. Insert 15 → [8,10,15] (3 keys, OK); insert 18 → [8,10,15,18] (4 keys) — overflow. Split into [8,10] and [15,18]; copy up 15. Root: [8,15].
Insert 23. Routes to the ≥15 leaf: [15,18,23] (3 keys, OK, no split).
Insert 25. [15,18,23,25] — overflow. Split into [15,18] and [23,25]; copy up 23. Root: [8,15,23] (3 keys — still within the order-4 capacity of 3).
Insert 28. Routes to the ≥23 leaf: [23,25,28] (OK).
Insert 31. [23,25,28,31] — overflow. Split into [23,25] and [28,31]; copy up 28. The root would now hold [8,15,23,28] — 4 keys, itself overflowing (root max is 3 keys). Root splits: with 4 keys/5 pointers temporarily in hand, the left half keeps ⌈4/2⌉=2 pointers and 1 key ([8], pointing at the two leftmost leaves), the median key 15 moves up to a brand-new root, and the right half keeps the remaining 3 pointers and keys [23,28]. The tree gains a level: Root=[15]; Left=[8]→leaves [2,5],[8,10]; Right=[23,28]→leaves [15,18],[23,25],[28,31].
Insert 33. Routes to the rightmost leaf: [28,31,33] (OK, no further split).
Question 1(a) — B+-tree after ascending inserts 2,5,8,...,33 (order 4)
Part (b) — the three operations, applied in turn to the tree above.
(i) Insert 24. 24 ≥ 15 routes into the right subtree; there, 23 ≤ 24 < 28 routes to the middle leaf [23,25]. Adding 24 gives [23,24,25] — only 3 keys, within capacity, so no split is needed anywhere.
Question 1(b)(i) — after insert 24
(ii) Delete 2. 2 lives in leaf A=[2,5]; removing it leaves A=[5], only 1 key — below the leaf minimum of 2. A's only sibling under the same parent, B=[8,10], is itself exactly at the minimum (2 keys) and has nothing to lend, so A and B merge into a single leaf [5,8,10] (3 keys, within capacity) and the separator "8" is dropped from the parent. That parent (previously keys=[8], 2 pointers) now has only 1 pointer left — an internal-node underflow (minimum is 2 pointers) — so it must borrow or merge with ITS sibling through the root. The root's right child [23,28] (3 pointers) has a pointer to spare, so it lends its leftmost pointer (leaf [15,18]) leftward: the root's old separator "15" moves down to become the new key of the left node (now [merged-leaf, [15,18]]), and the right node's own first key "23" moves up to become the new root separator. Result: Root=[23]; Left=[15]→leaves [5,8,10],[15,18]; Right=[28]→leaves [23,24,25],[28,31,33]. The tree's height is unchanged. Alternative (Silberschatz coalesce-first rule): because the underflowing internal node (1 pointer) and its sibling (3 pointers) together fit in one order-4 node, some texts coalesce them instead, pulling the root separator 15 down to give a single node [15,23,28] that becomes the new root (height drops to 2 levels). Either answer earns full marks if the rule is stated; applying (iii) to the coalesced tree overflows that root to [15,23,28,33], which splits back to exactly the same final tree shown below.
Question 1(b)(ii) — after delete 2 (leaves A,B merge; root borrows from R)
(iii) Insert 35. 35 ≥ 23 routes into the right subtree; there, 35 ≥ 28 routes to the rightmost leaf [28,31,33]. Adding 35 gives [28,31,33,35] — 4 keys, overflow. Split into [28,31] and [33,35]; copy up 33. The parent [28] (2 pointers) gains a key and pointer, becoming [28,33] with 3 pointers — within the order-4 capacity, so no further propagation. Root stays [23].
Question 1(b)(iii) — after insert 35 (leaf E splits)
