B-tree: find
General Information
Algorithmic problem: Sorted sequence: find
Type of algorithm: loop
Auxiliary data: A pointer [math]\displaystyle{ p }[/math] of type "pointer to a B-tree node of key type [math]\displaystyle{ \mathcal{K} }[/math]".
Abstract View
Invariant: After [math]\displaystyle{ i\geq 0 }[/math] iterations:
- pointer [math]\displaystyle{ p }[/math] points to some node of the B-tree on height level [math]\displaystyle{ i }[/math] and
- the searched key is in the range of that node.
Variant: [math]\displaystyle{ i }[/math] is increased by [math]\displaystyle{ 1 }[/math].
Break condition:
- [math]\displaystyle{ p }[/math] points to a leaf of the B-tree or (that is, inclusive-or)
- the searched key is in the node to which [math]\displaystyle{ p }[/math] points.
Remark: For example, the height of the subtree rooted at the node to which [math]\displaystyle{ p }[/math] points may be chosen as the induction parameter. For conciseness, the induction parameter is omitted in the following.
Induction Basis
Abstract view: p is initialized so as to point to the root of the B-tree.
Implementation: Obvious.
Proof: Obvious.
Induction Step
Abstract view:
- Let [math]\displaystyle{ N }[/math] denote the node to which [math]\displaystyle{ p }[/math] currently points.
- If the searched key is in [math]\displaystyle{ N }[/math], terminate the algorithm and return true.
- Otherwise, if [math]\displaystyle{ N }[/math] is a leaf, terminate the algorithm and return false.
- Otherwise, let [math]\displaystyle{ p }[/math] point the child of [math]\displaystyle{ N }[/math] such that the searched key is in the range of that child.
Implementation:
- If [math]\displaystyle{ K }[/math] is one of the values [math]\displaystyle{ p }[/math].keys[math]\displaystyle{ [1],\dots,p }[/math].keys[math]\displaystyle{ [p.n] }[/math], terminate the algorithm and return true.
- If [math]\displaystyle{ p }[/math].children[math]\displaystyle{ [0] = }[/math] void (that is, the current node is a leaf), terminate the algorithm and return false.
- If [math]\displaystyle{ K \lt p }[/math].keys[math]\displaystyle{ [1] }[/math] set [math]\displaystyle{ p := p }[/math].children[math]\displaystyle{ [0] }[/math].
- Otherwise, if [math]\displaystyle{ K \gt p }[/math].keys[math]\displaystyle{ [p.n] }[/math] set [math]\displaystyle{ p := p }[/math].children[math]\displaystyle{ [p.n] }[/math].
- Otherwise, there is exactly one [math]\displaystyle{ i \in \{1,\dots,p.n-1\} }[/math] such that [math]\displaystyle{ p }[/math].keys[math]\displaystyle{ [i] \lt K \lt p }[/math].keys[math]\displaystyle{ [i+1] }[/math].
- Set [math]\displaystyle{ p := p }[/math].children[math]\displaystyle{ [i] }[/math].
Correctness: Obvious.
Complexity
Statement: The asymptotic complexity is in [math]\displaystyle{ \Theta(T\cdot\log n) }[/math] in the worst case, where [math]\displaystyle{ T }[/math] is the complexity of the comparison and [math]\displaystyle{ n }[/math] the total number of keys in the B-tree.
Proof: Follows immediately from the the maximum height of the B-tree.
Pseudocode
B-TREE-FIND(x,k)
1 i = 1
2 while i ≤ x.n and k > x.keyi
3 i = i + 1
4 if i ≤ x.n and k == x.keyi
5 return (x.i)
6 elseif x.leaf
7 return NIL
8 else DISK-READ(x.ci)
9 return B-TREE-FIND(x.ci,k)