B-tree: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 4: Line 4:
https://openlearnware.tu-darmstadt.de/#!/resource/btrees-2134
https://openlearnware.tu-darmstadt.de/#!/resource/btrees-2134
http://huffmann.algo.informatik.tu-darmstadt.de/wiki/wiki.algo.informatik.tu-darmstadt.de/index.php/B-tree.html
http://huffmann.algo.informatik.tu-darmstadt.de/wiki/wiki.algo.informatik.tu-darmstadt.de/index.php/B-tree.html
== General information ==
'''Abstract data structure:''' [[Sorted sequence]]
Implementation Invariant:
# There is a number <math>M\in\mathbb{N}</math>, <math>M>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>M</math> is called the '''order''' of the B-tree.
# A B-tree of order <math>M</math> is a multi-way search tree with <math>2M-1</math slots for keys and, consequently, <math>2M</math> slots for children pointers, in each node.
## The slots for keys are denoted keyskeys.
## The slots for children are denoted childrenchildren.
# The attribute  stores the number of filled key slots.
# In each tree node except for the root, it is ; for the root, it is .
# The filled key slots are the ones at positions ; the filled child slots are the ones at positions  (except for leaves, of course, where no child slot is filled at all).
# The keys appear in ascending order in a B-tree node, that is, keyskeys for all .
# 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
## for ;
## for ;
## for .
# All leaves of a B-tree are on the same height level.

Revision as of 09:37, 26 May 2015

https://openlearnware.tu-darmstadt.de/#!/resource/btrees-2134 http://huffmann.algo.informatik.tu-darmstadt.de/wiki/wiki.algo.informatik.tu-darmstadt.de/index.php/B-tree.html

General information

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\lt /math slots for keys and, consequently, \lt math\gt 2M }[/math] slots for children pointers, in each node.
    1. The slots for keys are denoted keyskeys.
    2. The slots for children are denoted childrenchildren.
  3. The attribute stores the number of filled key slots.
  4. In each tree node except for the root, it is ; for the root, it is .
  5. The filled key slots are the ones at positions ; the filled child slots are the ones at positions (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, keyskeys for all .
  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.