StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The problem you have to understand what happens is because of the bad representation model you are using. You should have one data value associated with a pointer and the invariant that the data value is the smallest value in the subtree referenced by the pointer. </p> <p>So this is how you should represent the b-tree node prior of insertion. </p> <pre><code> 10|21|30|50| <--- root node 10|20| 21|22|25| 30|40| 50|60|80| <--- leaf nodes </code></pre> <p>In this representation the pointer after the value 10 in the root node points to the leaf node with the first value 10, etc.</p> <p>When you insert 23, it is inserted in the leaf node with first value of 21. This yields the following tree and no need to split. </p> <pre><code> 10|21|30|50| <--- root node 10|20| 21|22|23|25| 30|40| 50|60|80| <--- leaf nodes </code></pre> <p>When inserting 24 which produces the effect you described, what you get is the following </p> <pre><code> 10|30| <--- new root node 10|21|24| 30|50| <--- intermediate nodes 10|20| 21|22|23| 24|25| 30|40| 50|60|80| <--- leaf nodes </code></pre> <p>As you see there is no ambiguity anymore. The leaf node was split, and the key pointer pair 24| had to be inserted in the root node. Since it was full, it had to be split. Now that there are 5 values, you get one node with 3 values and one node with 2. You are free to choose if the left node or the right node get the three value. What is important is that the fundamental invariant is preserved. Each key value in a node is the smallest element in the subtree referenced by its associated pointer. A new root node had to be added and its key value pointer set should now be obvious. No ambiguity. </p> <p>This also makes obvious that many optimization strategies are possible. Instead of splitting the root node, we could have moved the value 21 into the left leaf node which was not full. The one with the first value 10. This avoids the need to split the root node and keeps the b-tree hight unchanged and yields a better filling of the b-tree. So you minimize space and search time. But this implies one can efficiently check if sideway balancing is feasible. A change of key value in the root node is still needed. etc.</p> <p>As you see, the value 10 in your b-tree is not really required in none leaf nodes and it is often omitted in b-tree representation (i.e. <a href="http://en.wikipedia.org/wiki/B+_tree" rel="nofollow">wikipedia</a>) but this can make it confusing and was probably the reason you where. :)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload