---

Other multiway search trees (Goodrich - Chapter 14.3)

---

• (a,b)-trees
  • (a,b)-tree:

    An (a,b)-tree is a multiway search tree where: Each internal node has ≥ a children, unless it is the root node Each internal node has ≤ b children All external nodes have the same depth (height) Since the number of keys (entries) is 1 less than the number of children, we can also say: a   ≤  # entries + 1   ≤   b Or: a − 1   ≤  # entries   ≤   b − 1            Requirement: 2  ≤  a  ≤  (b + 1)/2

  ---

  ---

• Insert into an (a,b)-tree
  • Insertion can cause a size violation:

    # entries in a node = b

    ---

  • Solution:

    split the node in 2 and link to the parent node Move the median valued key to the parent node Link the 2 (split) nodes to the parent node

    Example:

    ---

    ---

  • Note:

    This process is identical to the (2,4)-tree insertion procedure Example:

  ---

  ---

• Deleting an entry from an (a,b)-tree
  • Deletion can cause a (underflow) size violation:

    # entries in a node < a − 1

    ---

  • Solution:

    Transfer keys from sibling nodes And if sibling nodes are too small, merge: yourself and one of your sibling node and An entry from the parent node

    This procedure is also identical to the one in (2,4)-trees

  ---

  ---

• (2,4)-tree
  • The (2,4)-tree is a representative of the (a,b)-trees

  ---

  ---

• Another famous representative: B-tree
  • A B-tree is an externally stored tree

    I.e., the tree is stored on disk blocks !

    ---

  • The B-tree uses:

    b = number of records that fits maximally in one disk block a = ⌈ b/2 ⌉

    ---

  • Disk read operations already read one disk block at a time

  • These parameters allow a disk read operation to read one node per read operation

  • a = ⌈ b/2 ⌉ ensures that at least half of the disk block is filled with useful data