B-tree: find

From Algowiki
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:

  1. p points to some node N of the B-tree and
  2. 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:

  1. p points to a leaf of the B-tree or (that is, inclusive-or)
  2. the searched key is in the node to which p points.

Induction Basis

Induction Step

Complexity