B-tree: shift key to sibling

From Algowiki
Jump to: navigation, search

General Information

Algorithmic problem: See B-Trees

Type of algorithm: loop

Auxiliary data:

Abstract View

Invariant: After [math]i \ge 0[/math] iterations:

  1. If [math] shiftRight[/math]
    1. For [math]j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \{[/math], if [math]j\gt 0[/math], the original values of [math]p.children[k].key[j][/math] are now the values of [math]p.children[k].key[j+1][/math].
    2. For [math]j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \}[/math], the original values of [math]p.children[k].children[j][/math] are now the values of [math]p.children[k].children[j+1][/math].
  2. Otherwise:
    1. For [math]j \in \{2, \dots ,i+1 \}[/math], id [math]j \le n[/math], the original values of [math]p.children[k].key[j][/math] are now the values of [math]p.children[k].key[j-1][/math].
    2. For [math]j \in \{ 1, \dots ,i \}[/math], the values of [math]p.children[k].children[j][/math] are now the values of [math]p.children[k].children[j-1][/math].
    3. A few moves have already been done (in the preprocessing, in fact):
      1. The former value of [math]p.keys[k][/math] is now the node [math]p.children[k-1][/math].
      2. The former value of [math]p.children[k].keys[1][/math] is now at [math]p.keys[k][/math].
      3. The children pointers of [math]p.children[k-1][/math] and [math]p.children[k][/math] are rearranged accordingly.

Vairant: [math]i[/math] increases by [math]1[/math]

Break condition: [math](shiftRight[/math][math] i=p.children[k].n+1)[/math][math]([/math]¬[math]shiftRight[/math][math]i=p.children[k].n)[/math]

Before and after each iteration, [math]p[/math] points to a node [math]N[/math] such that the following holds:

  1. In the case [math]p.n \lt 2M[/math], all implementation invariants of B-trees are maintained if the following [math]K'[/math] can be inserted at some position in [math]N[/math] such that after insertion.
  2. In the case [math]p.n = 2M[/math], imagine that we could extend [math]p[/math].keys by one more slot (and, consequently, extend .successors by one more slot). Then [math]K'[/math] can be inserted in [math]N[/math] at a position such that - except for the statement about the size of [math]N[/math] - all implementation invariants of B-trees are again maintained after insertion.

Variant: The height level of the node to which [math]p[/math] points is decreased by [math]1[/math].

Break condition: [math]p.N \lt 2M[/math] or (that is, inclusive-or) [math]p[/math] points to the root.

Induction Basis

Abstract view:

Implementation:

Proof:

Induction Step

Abstract view:

  1. Move the next key and children pointer.
  2. If [math]shiftRight[/math] and the break condition applies, the shift is to be done.

Implementation:

  1. If [math]shiftRight[/math]:
    1. If [math]i \le n[/math], set [math]p.children[k]keys[p.children[k].n-i+2]:= p.children[k],keys[p.children[k]._n-i+1][/math]
    2. Set [math]p.children[k].children[p.children[k]._n-i+2]:= p.children[k].children[p.children[k]_n-i+1][/math]
    3. If [math] i=n+1[/math]:
      1. Set [math]p.children[k].keys[1]:= p.keys[k][/math]
      2. Set [math]p.keys[k]:=p.children[k-1].keys[p.children[k-1]_n] [/math]
      3. Increment [math]p.children[k]_n by one [/math]
      4. Decrement [math]p.children[j-1]_n by one[/math]
  2. Otherwise:
    1. If [math]i\lt p.children[k]_n[/math] set [math]p.children[k].keys[i]:= p.children[k].keys[i+1][/math]
    2. Set [math]p.children[k].children[i-1]:= p.children[k].children[i][/math]
    3. If [math]i=p.children[k]_n, [/math]decrement [math]p.children[k]_n[/math] by one

Correctness:

  1. For the rearrangement of the children pointers, compare the induction basis.
  2. Note that the increments and decrements of [math]p.children[k-1]_n[/math] and [math]p.children[k]_n [/math] are distributed over induction basis and induction step, but are correct in summary.

Complexity

Statement: Linear in [math]M[/math] in the best and worst case (and hence constant for fixed [math]M[/math]). Proof: Obvious.