B-tree: find
Jump to navigation
Jump to search
General Information
Algorithmic problem: Sorted sequence: find
Type of algorithm: loop
Auxiliary data: A pointer p of type "pointer to a B-tree node".
Abstract View
Invariant: Before and after each iteration:
- p points to some node N of the B-tree and
- the searched key is in the range of N.
Variant: p is redirected from the current node N to some child of the current node.
Break condition:
- p points to a leaf of the B-tree or (that is, inclusive-or)
- the searched key is in the node to which p points.
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 N denote the node to which p currently points.
- If the searched key is in N, terminate the algorithm and return true.
- Otherwise, if N is a leaf, terminate the algorithm and return false.
- Otherwise, let p point the child of N such that the searched key is in the range of that child
Implementation:
- If K is one of the values [math]\displaystyle{ p.keys[1],\dots,p.keys[p.n] }[/math], terminate the algorithm and return true.
- If [math]\displaystyle{ p.children[0] = void }[/math] (that is, the current node is a leaf), terminate the algorithm and return false.
- If [math]\displaystyle{ K \lt p.keys[1] }[/math] set [math]\displaystyle{ p := p.children[p.n] }[/math].
- Otherwise, if [math]\displaystyle{ K \gt p.keys[p.n]\lt /math set \lt math\gt p := p.children[p.n] }[/math].
- Otherwise, there is exactly one [math]\displaystyle{ i \in \{1,\dots,p.n-1\} }[/math] such that [math]\displaystyle{ p.keys[i] \lt K \lt p.keys[i+1] }[/math].
- Set [math]\displaystyle{ p := p.children[i] }[/math].
Correctness: Obvious.
Pseudocode
B-TREE(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)
Complexity
Statement: The asymptotic complexity is in [math]\displaystyle{ \Theta(\log n) }[/math] in the worst case.
Proof: Follows immediately from the fact that the height of B-tree with n nodes is in [math]\displaystyle{ \Theta(\log n) }[/math] (cf. the remark clause of the B-Trees page).