B-tree: find
General Information
Algorithmic problem: Sorted sequence: find
Type of algorithm: loop
Auxiliary data: A pointer
Abstract View
Invariant: After
- pointer
points to some node of the B-tree on height level and - the searched key is in the range of that node.
Variant:
Break condition:
points to a leaf of the B-tree or (that is, inclusive-or)- the searched key is in the node to which
points.
Remark: For example, the height of the subtree rooted at the node to which
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
denote the node to which currently points. - If the searched key is in
, terminate the algorithm and return true. - Otherwise, if
is a leaf, terminate the algorithm and return false. - Otherwise, let
point the child of such that the searched key is in the range of that child.
Implementation:
- If
is one of the values .keys .keys , terminate the algorithm and return true. - If
.children void (that is, the current node is a leaf), terminate the algorithm and return false. - If
.keys set .children . - Otherwise, if
.keys set .children . - Otherwise, there is exactly one
such that .keys .keys . - Set
.children .
Correctness: Obvious.
Complexity
Statement: The asymptotic complexity is in
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)