B-tree: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 7: | Line 7: | ||
'''Implementation Invariant:''' | '''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. | # 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. | # A B-tree of order <math>M</math> is a [[Multi-way search tree|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 keys<math>[1],\ldots,</math>keys<math>[2M\!-\!1]</math>. | ## The slots for keys are denoted keys<math>[1],\ldots,</math>keys<math>[2M\!-\!1]</math>. | ||
## The slots for children are denoted children<math>[1],\ldots,</math>children<math>[2M]</math>. | ## The slots for children are denoted children<math>[1],\ldots,</math>children<math>[2M]</math>. | ||
| Line 14: | Line 14: | ||
# The filled key slots are the ones at positions <math>1,\ldots,n</math>; the filled children slots are the ones at positions <math>0,\ldots,n</math> (except for leaves, of course, where no child slot is filled at all). | # The filled key slots are the ones at positions <math>1,\ldots,n</math>; the filled children slots are the ones at positions <math>0,\ldots,n</math> (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, keys<math>[i]<</math> keys<math>[i\!+\!1]</math> for all <math>i\in\{1,\ldots,n-1\}</math>. | # The keys appear in ascending order in a B-tree node, that is, keys<math>[i]<</math> keys<math>[i\!+\!1]</math> for all <math>i\in\{1,\ldots,n-1\}</math>. | ||
# 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 | # The children pointers appear in the order as used in the definition of [[Multi-way search tree|multi-way search trees]]. In other words, for , the [[Directed tree#Range|range]] of the node to which points is | ||
## for ; | ## for ; | ||
## for ; | ## for ; | ||
## for . | ## for . | ||
# All leaves of a B-tree are on the same height level. | # All leaves of a B-tree are on the same height level. | ||
Revision as of 10:07, 26 May 2015
Abstract data structure: Sorted sequence
Implementation Invariant:
- 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.
- 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.
- The slots for keys are denoted keys[math]\displaystyle{ [1],\ldots, }[/math]keys[math]\displaystyle{ [2M\!-\!1] }[/math].
- The slots for children are denoted children[math]\displaystyle{ [1],\ldots, }[/math]children[math]\displaystyle{ [2M] }[/math].
- The attribute [math]\displaystyle{ n }[/math] of a node stores the number of filled key slots in this node.
- In each tree node except for the root, it is [math]\displaystyle{ n\geq M-1 }[/math]; for the root, it is [math]\displaystyle{ n\geq 1 }[/math].
- The filled key slots are the ones at positions [math]\displaystyle{ 1,\ldots,n }[/math]; the filled children 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).
- 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].
- 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.