B-Trees

From

(Difference between revisions)
Jump to: navigation, search
(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:

  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.

Personal tools
MediaWiki Appliance - Powered by TurnKey Linux