Updates on a cache-oblivious B-tree 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 ﬁrst 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 ﬁnd 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$ &lt; ρ(v) &lt; $τ_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$.
Perhaps one must consider the parent of the node to be inserted as having weight 2. Then the "find the lowest in-density ancestor" is equivalent to "find the least amount of rebuilding needed to maintain the invariants".

edit:

In the physical world, density is defined as mass divided by volume. This corresponds to the density notion in these cache-oblivious B-trees if we view each "item" as having mass 1 and each location in $\mathcal{T&#39;}$ (the static binary tree) as having volume 1.

Before inserting an item, we want to make sure that once it is in the tree it is in a subtree that is within its prescribed density bounds. We therefore imagine that it is already there in the tree, but taking up no space yet. The reason why we might imagine that it presently takes up no space is that, well, there might not be any space for it to take up right now, as in your example.

To make sure that the tree the new item will be in is within bounds, we need to find its closest ancestor that we actually can rebalance (without increasing the height) and insert the item into while still remaining within the density boundaries. To do so, we find the nearest ancestor that will be within the density boundaries, which means using its current "volume" and its soon-to-be-correct "mass". To get the latter, we must include an extra unit of mass for the item we are about to insert.