B-Trees
From
(Created page with '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. <br/><br/> Part of the de...') |
m (Protected "B-Trees" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite))) |
Revision as of 15:37, 29 March 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:
- The root is either a leaf or has at least 2 children.
- Each node, except for the root and the leaves has between ⎡m/2⎤ and m children.
- 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.
