B-tree: shift key to sibling

General Information

Algorithmic problem: See B-Trees

Type of algorithm: loop

Auxiliary data:

Abstract View

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

1. If [math]\displaystyle{ shiftRight }[/math]
   1. For [math]\displaystyle{ j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \{ }[/math], if [math]\displaystyle{ j\gt 0 }[/math], the original values of [math]\displaystyle{ p.children[k].key[j] }[/math] are now the values of [math]\displaystyle{ p.children[k].key[j+1] }[/math].
   2. For [math]\displaystyle{ j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \} }[/math], the original values of [math]\displaystyle{ p.children[k].children[j] }[/math] are now the values of [math]\displaystyle{ p.children[k].children[j+1] }[/math].
2. Otherwise:
   1. For [math]\displaystyle{ j \in \{2, \dots ,i+1 \} }[/math], id [math]\displaystyle{ j \le n }[/math], the original values of [math]\displaystyle{ p.children[k].key[j] }[/math] are now the values of [math]\displaystyle{ p.children[k].key[j-1] }[/math].
   2. For [math]\displaystyle{ j \in \{ 1, \dots ,i \} }[/math], the values of [math]\displaystyle{ p.children[k].children[j] }[/math] are now the values of [math]\displaystyle{ 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]\displaystyle{ p.keys[k] }[/math] is now the node [math]\displaystyle{ p.children[k-1] }[/math].
      2. The former value of [math]\displaystyle{ p.children[k].keys[1] }[/math] is now at [math]\displaystyle{ p.keys[k] }[/math].
      3. The children pointers of [math]\displaystyle{ p.children[k-1] }[/math] and [math]\displaystyle{ p.children[k] }[/math] are rearranged accordingly.

Vairant: [math]\displaystyle{ i }[/math] increases by [math]\displaystyle{ 1 }[/math]

Break condition: [math]\displaystyle{ (shiftRight }[/math] ∧[math]\displaystyle{ i=p.children[k].n+1) }[/math]∨[math]\displaystyle{ ( }[/math]¬[math]\displaystyle{ shiftRight }[/math]∧[math]\displaystyle{ i=p.children[k].n) }[/math]

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

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

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

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

Induction step

Abstract view:

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

Implementation:

1. If [math]\displaystyle{ shiftRight }[/math]:
   1. If [math]\displaystyle{ i \le n }[/math], set [math]\displaystyle{ p.children[k]keys[p.children[k].n-i+2]:= p.children[k],keys[p.children[k]._n-i+1] }[/math]
   2. Set [math]\displaystyle{ p.children[k].children[p.children[k]._n-i+2]:= p.children[k].children[p.children[k]_n-i+1] }[/math]
   3. If [math]\displaystyle{ i=n+1 }[/math]:
      1. Set [math]\displaystyle{ p.children[k].keys[1]:= p.keys[k] }[/math]
      2. Set [math]\displaystyle{ p.keys[k]:=p.children[k-1].keys[p.children[k-1]_n] }[/math]
      3. Increment [math]\displaystyle{ p.children[k]_n by one }[/math]
      4. Decrement [math]\displaystyle{ p.children[j-1]_n by one }[/math]
2. Otherwise:
   1. If [math]\displaystyle{ i\lt p.children[k]_n }[/math] set [math]\displaystyle{ p.children[k].keys[i]:= p.children[k].keys[i+1] }[/math]
   2. Set [math]\displaystyle{ p.children[k].children[i-1]:= p.children[k].children[i] }[/math]
   3. If [math]\displaystyle{ i=p.children[k]_n, }[/math]decrement [math]\displaystyle{ 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]\displaystyle{ p.children[k-1]_n }[/math] and [math]\displaystyle{ p.children[k]_n }[/math] are distributed over induction basis and induction step, but are correct in summary.

Complexity

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