Hye, I have started to read and implement Cache Oblivious Btree on RAM. Starting with the Weight Balanced BTree by Arge and Vitter. The Deletion algorithm explained says that after deletion of a leaf an ancestor will get unbalanced so to merge the ancestor with neighbor and split if the weight goes above the max range.
"Deletions. Deletions are similar to insertions. As before,we search down the tree to find which leaf w to delete. After deleting w, some ancestors of w may become unbalanced.That is, some ancestor node u at height h may have weight lower than (1/2)d^(h-1). As before, we bring the ancestors of w into balance starting from the ancestors closest to the leaves. We merge u with one of its neighbors. After merging u, however, it might now have a weight larger than its upper bound, so we immediately split it into two nodes as described in the insertion algorithm. (This may alternatively be viewed as u stealing children from its neighbor.)"
The same algo in the original paper says to use global rebuilding techniques.
My questions are:
1.What is the "Global Rebuilding" technique exactly?
2.Is the deletion algorithm correct? I used the deletion algo of Btree (as explained in the book by Thomas Cormen)and just replaced min with the minimum range of the Weight Balanced Btree required and cant seem to find where the above condition will occur.
Some clarity on the questions would really be appreciated. Any other inputs are also welcome.Thanks.
If anyone has implemented the same on windows than the code would be highly appreciated for detailed understanding.(Purely for knowledge purpose. No form of cheating or homework)