M-ary Search tree

  • Binary search tree has one key to decide which of the two branches to take

  • M-ary search tree needs M-1 keys to decide which branch to take

  • M-ary search tree should be balanced in some way.

    • We don’t want an M-ary search tree to degenerate to a linked list, or even a binary search tree

  • Thus, require that each node is at least half full!

Definition

  • A B+ tree of order M
  • Each internal node has at most M children (M-1 keys)
  • Each internal node, except the root, has between and keys
    Each leaf has between keys and corresponding data items

  • A of order M (M>3) is an M-ary tree with the following properties:

  • The data items are stored in leaves

  • The root is either a leaf or has between two and M children

  • The non-leaf nodes store up to M-1 keys to guide the searching; key i represents the smallest key in subtree i+1

  • All non-leaf nodes (except the root) have between and M children

  • All leaves are at the same depth and have between and L data items, for some L (usually L << M, but we will assume M=L in most examples)

  • Keys in internal Nodes

  • key i in an internal node is the smallest key in its i+1 subtree (i.e. right subtree of key i)

Insertion

  1. Suppose that we want to insert a key K and its associated record.
  2. Search for the key K using the search procedure. This will bring us to a leaf x
  3. Insert K into x

Insert Into Leaf

  • If leaf x contains < L keys, then insert K into x (at the correct position in node x)
  • If x is already full (i.e. containing L keys) then split x
    • Cut x off from its parent
    • Insert K into x, pretending x has space for K. Now x has L+1 keys.
    • After inserting K, split x into 2 new leaves and , with containing the smallest keys, and containing the remaining keys. Let J be the minimum key in
    • Make a copy of J to be the parent of and , and insert the copy together with its child pointers into the old parent of x.

Insert Into Internal Node When leaf is Full and Internal Node is also Full

To insert a key K into a full internal node x:

  • Cut x off from its parent
  • Insert K and its left and right child pointers into x, pretending there is space. Now x has M keys (and M+1 pointers).
  • Split x into 2 new internal nodes and , with containing the smallest keys, and containing the largest keys. Note that the key J is not placed in or
    Make J the parent of xL and xR, and insert J together with its child pointers into the old parent of x.

Deletion

Situation I:

  • The target is a key in some internal node (needs to be replaced, according to our convention)

Situation II:

  • After deleting target from leaf x, x contains less than keys (needs to merge nodes)

Situation I Removal of a Key

After deleting from node x, we can access y directly and replace target by the new smallest key in x

Situation II Handling Leaves with Too Few Keys

Let u be the leaf that has keys (too few)
Let v be a sibling of u with at least keys
Let k be the key in the parent of u and v that separates the pointers to u and v
There are two cases

Case I

Case 1: v contains or more keys and v is the right sibling of u
Move the leftmost record from v to u

Case 2

v contains or more keys and v is the left sibling of u
Move the rightmost record from v to u
Then set the key in parent of u that separates u and v to be the new smallest key in u

Table Of Contents
M-ary Search tree
Definition
Insertion
Deletion
Situation I Removal of a Key
Situation II Handling Leaves with Too Few Keys
Case I
Case 2