B-tree: shift key to sibling: Difference between revisions

From Algowiki
Jump to navigation Jump to search
(Created page with "Category:B-Tree Category:Algorithm == General Information == '''Algorithmic problem:''' See B-tree '''Type of algorithm:''' loop '''Auxiliary data:''' == Abstr...")
 
No edit summary
 
(10 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[Category:Videos]]
{{#ev:youtube|https://www.youtube.com/watch?v=vbRZ8h6ROYc|500|right||frame}}
[[Category:B-Tree]]
[[Category:B-Tree]]
[[Category:Algorithm]]
[[Category:Algorithm]]
== General Information ==
== General Information ==
'''Algorithmic problem:''' [[See B-tree]]
'''Algorithmic problem:''' [[B-Trees|See B-Trees]]


'''Type of algorithm:''' loop
'''Type of algorithm:''' loop


'''Auxiliary data:'''  
'''Auxiliary data:'''


== Abstract View ==
== Abstract View ==
Line 19: Line 21:
### The former value of <math>p.keys[k]</math> is now the node <math>p.children[k-1]</math>.
### The former value of <math>p.keys[k]</math> is now the node <math>p.children[k-1]</math>.
### The former value of <math>p.children[k].keys[1]</math> is now at <math>p.keys[k]</math>.
### The former value of <math>p.children[k].keys[1]</math> is now at <math>p.keys[k]</math>.
### The children pointers of <math>p.children[k-1]</math> and <math>p.children[k]</math are rearranged accordingly.
### 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>
'''Vairant:''' <math>i</math> increases by <math>1</math>
Line 32: Line 34:


'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.
== Induction Basis ==


== Induction Basis ==
=== Abstract view: ===
'''Abstract view:'''
 
# <math>p</math> is set to the input pointer.
=== Implementation: ===
# <math>p_1</math> and <math>p_2</math> are void initially.


'''Implementation:''' Obvious.
=== Proof: ===


'''Proof:''' The requirement on the input pointer immediately implies the invariants.


== Induction Step ==
== Induction Step ==
'''Abstract view:'''
=== Abstract view: ===
# If the node is not full, the key can be inserted, and we are done.
# Move the next key and children pointer.
## If the new key is larger than all keys stored in the node, it can be appended.
# If <math>shiftRight</math> and the break condition applies, the shift is to be done.
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.
## <math>N_1</math>  will contain all keys strictly less than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }
## Analogously, <math>N_2</math> will contain all keys strictly greater than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }.
## Next we try to
## If <math>K'</math> is that median itself, nothing is to be done on the current node.
## Otherwise, the median of <math>\{p.keys[1], \dots , p.keys[p.n], K'\}</math>  is in one of the slots of the node. This slot is overridden (by moving the contents of each slot to the right one position further left). The previous contents of this slot is the new <math>K'</math> . If the current node is the root, which we next try to insert in the predecessor of


'''Implementation:'''
=== Implementation: ===
# If <math>p.n = 2M</math>
# If <math>shiftRight</math>:
## If <math>p.keys[M] < K' < p.keys[M + 1]</math>, break the iteration and continue the loop.
## 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>
## Otherwise: <math> x:= M</math> if <math> K' < p.keys[M]</math>, and <math> x:= M+1</math> otherwise.
## Set <math>p.children[k].children[p.children[k]._n-i+2]:= p.children[k].children[p.children[k]_n-i+1]</math>
## Set <math> K'' := p.keys[x]</math>.
## If <math> i=n+1</math>:
## For <math> j \in \{x+1, \dots, p.n \}</math> (in this order), set <math> p.keys [j-1]:= p.keys[j] </math> and <math>p. successor[j-1]:= p.successors[j]</math>.
### Set <math>p.children[k].keys[1]:= p.keys[k]</math>
# If <math> p.keys[p.n] < K'</math>, insert the new (key, value)-pair at position <math>p.keys[p.n+1</math>
### Set <math>p.keys[k]:=p.children[k-1].keys[p.children[k-1]_n] </math>
### Increment <math>p.children[k]_n by one </math>
### Decrement <math>p.children[j-1]_n by one</math>
# Otherwise:
# Otherwise:
## Let <math>i \in \{ 1, \dots , p.n \} </math> be minimal subject to <math>K' < p.keys[i]</math>
## If <math>i<p.children[k]_n</math> set <math>p.children[k].keys[i]:= p.children[k].keys[i+1]</math>
## For <math> j \in \{ p.n, \dots , i \} </math> (in this order), set <math> p.keys[j+1]:= p.keys[j]. </math>
## Set <math>p.children[k].children[i-1]:= p.children[k].children[i]</math>
# If <math> p.n < 2M</math>, set <math> p.n:= p.n+1</math> and terminate the algorithm.
## If <math>i=p.children[k]_n, </math>decrement <math>p.children[k]_n</math> by one
# Otherwise, set <math>K':= K''</math>.


'''Correctness:''' Easy to see.
=== Correctness: ===
# For the rearrangement of the children pointers, compare the induction basis.
# 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 ==
== Complexity ==
'''Statement:''' Linear in <math>M</math> in the best and worst case (and hence constant for fixed <math>M</math>).
'''Proof:''' Obvious.

Latest revision as of 23:17, 19 June 2015

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 Basis

Abstract view:

Implementation:

Proof:

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.

Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_shift_key_to_sibling&oldid=3379"