B-Trees

From

Revision as of 10:09, 13 May 2009

A tree structure that is very useful is called a B-Tree. There are several extensions or variation to the basic B-Tree: B+-Tree, B*-Tree, and B′-Tree.

Part of the definition, or description, of a B-Tree is an order. The order relates to how many children a node in a B-Tree has.

Behavior of a B-Tree

A B-Tree of order m has the following properties:

1. The root is either a leaf or has at least 2 children.
2. Each node, except for the root and the leaves has between ⎡m/2⎤ and m children.
3. All leaves are at the same level in the tree.

As a consequence of the definition, the following can be said about a B-Tree:

• B-Trees are always height balanced, with all leaf nodes at the same level.
• Update and search operations affect only a few nodes, so performance is good.
• A B-Tree guarantees that every node in the tree will be full up to a minimum percentage. This improves space efficiency and reduces the number of memory fetches during a search operation.

Example of a B-Tree

In this example, we will use a B-Tree of order 4. This means that each node can store up to 4 pointers, i.e. have 4 children, and 3 keys. Internal nodes must have between 2 and 4 children. This example is a power point presentation. As part of this example, we will consider how a node splits when it overflows, and how two nodes recombine when they underflow.