Lecture Notes for CS 512, Algorithm Design

B-Trees - 14 February 2000

1. sometimes a large height is a problem

   1. a huge number of keys

   2. expensive node access - imagine accessing each red-black tree node via the www

2. the solution to both problems is to increase the node branching

3. b-trees

   1. each n node has

      1. n.keycnt keys

      2. n.keys[1] <= n.keys[2] <= ... <= n.keys[n.keycnt]

      3. n.leaf

   2. internal nodes have n.keycnt + 1 children, n.children[1], ...

   3. the bst property: n.children[i].key[..] <= n.key[i] <= n.children[i + 1].key[..]

   4. leaves are at the same depth - perfectly balanced

   5. each b-tree has a minimum degree t

      1. non-root nodes have at least t - 1 keys and t children for internal nodes

      2. every node has at most 2t - 1 keys and 2t children for internal nodes

4. searching for a key

5. creating a new b-tree

6. splitting a node n

   1. n has 2t - 1 keys; don't split nonfull nodes

   2. n's median key moves into the parent

   3. the parent must not be full

   4. if n is the root, the b-tree grows by one level

7. expensive node access means one-pass traversals are important

   1. make sure a node isn't too full before trying to insert

   2. make sure a node isn't too empty before trying to delete

8. inserting a key

   1. to avoid the 2t - 1 problem, split the next node before recursing to it

   2. insert the key in a leaf node

9. deleting a key k

   1. to avoid the t - 1 problem, make sure a node has at least t keys before recursing to it

   2. if k is in a leaf, delete it

   3. if k is in an interior node n, use the bst trick: replace the key with its predecessor or successor

      1. if k's left child has at least t keys, find k's predecessor in the left child, delete it, and replace k with its predecessor in n

      2. if k's right child has at least t keys, find k's predecessor in the right child, delete it, and replace k with it's predecessor in n

      3. merge the two t - 1 subtrees with the key, delete the key and the former right subtree from the interior node, and recurse to the new child

   4. if the key isn't in the interior node

      1. find the child that might contain the key

      2. if the child has only t - 1 keys

         1. move a key from a sibling with at least t keys

            1. move the interior-node key between the child and its sibling down into the child

            2. move the proper sibling key (leftmost or rightmost) up into the interior node to replace the moved key

            3. shift the key-less child pointer from the sibling to the child

         2. merge the child with a t - 1 key sibling

            1. the new child is the old child, the key between the child and sibling, and the sibling

            2. shift the keys and children in the interior node to compress out the old key and sibling pointer

This page last modified on 16 February 2000.