Skip to main content

B-tree properties; order 5 for 3, 14, 7, ...

Short answer

B-tree properties: max m children, min ⌈m/2⌉ children for non-root, all leaves same level, keys sorted, tree balanced. Constructed order-5 B-tree: root [7 13] with leaves [1 3 5] [8 11] [14 17].

Write down the properties of B-tree. Construct a B-tree of order 5 for following data: 3, 14, 7, 1, 8, 5, 11, 17, and 13.

Properties of a B-tree of order m

  1. Every node has at most m children, i.e. at most m − 1 keys.
  2. Every non-root, non-leaf node has at least ⌈m/2⌉ children (and every non-root node has at least ⌈m/2⌉ − 1 keys).
  3. The root has at least 2 children if it is not a leaf.
  4. A node with k children holds k − 1 keys, stored in ascending order.
  5. All leaves are on the same level, so the tree is perfectly height-balanced.
  6. For a node with keys k₁ < k₂ < ..., the subtree to the left of k₁ holds keys smaller than k₁, the subtree between kᵢ and kᵢ₊₁ holds keys that lie between them, and the subtree to the right of the last key holds larger keys.
  7. The tree grows and shrinks at the root; search, insert and delete take O(log n).

B-tree of order 5 (max 4 keys, min 2 keys per non-root node)

StepInsertTree after stepAction
13[3]fits in leaf
214[3 14]fits in leaf
37[3 7 14]fits in leaf
41[1 3 7 14]fits in leaf
58[7]{[1 3], [8 14]}leaf [1 3 7 8 14] overflows, split: 7 moves up; new root
65[7]{[1 3 5], [8 14]}fits in leaf
711[7]{[1 3 5], [8 11 14]}fits in leaf
817[7]{[1 3 5], [8 11 14 17]}fits in leaf
913[7 13]{[1 3 5], [8 11], [14 17]}leaf [8 11 13 14 17] overflows, split: 13 moves up

Final tree

[7 13]
[1 3 5]  [8 11]  [14 17]

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 6 questions →