Contents    Page-10    Prev    Next    Page+10    Index   

B-Tree Implementation

Conceptually, an interior node is an array of n pointers and n - 1 key values. A pointer is between the two key values that bound the entries that it covers; we imagine that the array is bounded by key values of - ∞ and . (In practice, two arrays, pointers and key values, may be used since they are of different types.)

Binary search of the array of key values can be used to find the right pointer to follow. If we have the sequence
         keyi pointeri keyi+1
pointeri covers all keys such that keyi ≤ key < keyi+1.