B-tree

From Algowiki
Revision as of 09:51, 26 May 2015 by Weihe (talk | contribs)
Jump to navigation Jump to search


Abstract data structure: Sorted sequence

Implementation Invariant:

  1. There is a number [math]\displaystyle{ M\in\mathbb{N} }[/math], [math]\displaystyle{ M\gt 1 }[/math], which is specific for the B-tree object and is constant throughout the life time of the B-tree object. This value [math]\displaystyle{ M }[/math] is called the order of the B-tree.
  2. A B-tree of order [math]\displaystyle{ M }[/math] is a multi-way search tree with [math]\displaystyle{ 2M-1 }[/math] slots for keys and, consequently, [math]\displaystyle{ 2M }[/math] slots for children pointers, in each node.
    1. The slots for keys are denoted keys[math]\displaystyle{ [1],\ldots, }[/math]keys[math]\displaystyle{ [2M\!-\!1] }[/math].
    2. The slots for children are denoted children[math]\displaystyle{ [1],\ldots, }[/math]children[math]\displaystyle{ [2M] }[/math].
  3. The attribute [math]\displaystyle{ n }[/math] of a node stores the number of filled key slots in this node.
  4. In each tree node except for the root, it is [math]\displaystyle{ n\geq M }[/math]; for the root, it is [math]\displaystyle{ n\geq 1 }[/math].
  5. The filled key slots are the ones at positions [math]\displaystyle{ 1,\ldots,n }[/math]; the filled child slots are the ones at positions [math]\displaystyle{ 0,\ldots,n }[/math] (except for leaves, of course, where no child slot is filled at all).
  6. The keys appear in ascending order in a B-tree node, that is, keys[math]\displaystyle{ [i]\lt }[/math]keys[math]\displaystyle{ [i\!+\!1] }[/math] for all [math]\displaystyle{ i\in\{1,\ldots,n-1\} }[/math].
  7. The children pointers appear in the order as used in the definition of multi-way search trees. In other words, for , the range of the node to which points is
    1. for ;
    2. for ;
    3. for .
  8. All leaves of a B-tree are on the same height level.