# B-tree: shift key to sibling

(Redirected from B-Tree:Shift Key to Sibling)

## General Information

Algorithmic problem: See B-Trees

Type of algorithm: loop

Auxiliary data:

## Abstract View

Invariant: After $i \ge 0$ iterations:

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

Vairant: $i$ increases by $1$

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

Before and after each iteration, $p$ points to a node $N$ such that the following holds:

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

Variant: The height level of the node to which $p$ points is decreased by $1$.

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

## Induction Step

### Abstract view:

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

### Implementation:

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

### Correctness:

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

## Complexity

Statement: Linear in $M$ in the best and worst case (and hence constant for fixed $M$). Proof: Obvious.