B-tree

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 }[/math] slots for keys and, consequently, [math]\displaystyle{ 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.