B-Trees
From
m (Protected "B-Trees" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite))) |
(→Example of a B-Tree) |
||
| Line 17: | Line 17: | ||
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. | 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. | ||
<br/><br/> | <br/><br/> | ||
| + | ---- | ||
| + | {{CS2/ChapNav}} | ||
| + | ---- | ||
| + | [[Category:CS2|{{SUBPAGENAME}}]] | ||
Revision as of 17:08, 9 April 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.
CS2: Data Structures
Theory of Computation - ADT Preliminaries
Linear ADTs - Tree ADTs - Graph ADTs - Unordered Collection ADTs
