Lately I have been studying cache-oblivious data structures and algorithms. I was reading about the cache-oblivious B-tree from the Handbook of Data Structures and Applications, with hopes of actually implementing it and doing some benchmarking.
Section 38.3.1 of the book talks about the density based approach. The vEB-layout and the density thresholds seem fine, but I am missing something (perhaps even trivial) from the updates. The text explains:
To insert a new element into the structure we first locate the position in $T$ of the new node $w$. If the insertion of $w$ violates the height bound $H$, we rebalance $T$ as follows: First we find the lowest ancestor v of w satisfying $γ_i$ ≤ ρ(v) ≤ $τ_i$, where $i$ is the level of $v$.
Looking at the figure, let's consider a scenario: suppose we want to insert an item with value 15. We check to see that it cannot be inserted since the height bound $H$ would be violated. Hence we must find the lowest ancestor $v$ of $w$ satisfying the mentioned bounds. If we now work towards the top of tree trying to find a suitable ancestor, we find it immediately (the item with value 13). It clearly satisfies the bounds, since its ρ is 1.
It would make a lot more sense to me if the ancestor at which we should stop is the one with value 8. Right now I see two cases: either I don't know the exact definition of lowest ancestor or the lowest ancestor $v$ should satisfy not $γ_i$ ≤ ρ(v) ≤ $τ_i$ but $γ_i$ < ρ(v) < $τ_i$.
I also took a look at Cache-oblivious B-trees by Bender, Demaine and Farach-Colton. This paper also defines the bound as $γ_i$ ≤ ρ(v) ≤ $τ_i$.