I have a balanced $k$-ary B-tree with $N$ leaves (where N is a power of $k$ for simplicity) and I need to simultaneously locate $l$ leaves in it. What is the expected number of nodes I will need to traverse? Obviously for $l=1$ we need to traverse $log_k(N)$ nodes but the question becomes less trivial (for me) for larger $l$s. My attempt at $l=2$ and $k=2$:

Without loss of generality, the first query is in the leftmost leaf. We have at least First, we traverse the root. Then out of all the possible places where the other query one can be, there’s a $2^{N-1}$ chance that we will need to follow different paths for each of the nodes, and that would mean the total nodes to be traversed is $2 log(N) – 1$. In the rest of the cases we have the same problem only we are down to $frac{N}{2}$ leaves, only we have already traversed the root. So the expected leaves would be

$$

begin{align}

f(2) &:= 2 \

f(N) &:= frac{1}{2}(2 log(N) – 1) + frac{1}{2}(f(frac{N}{2}) + 1) = log(N)+frac{f(frac{N}{2})}{2}

end{align}

$$

So that would become

$$

f(N) = sum_{i}frac{log(N)-i}{2^i}

$$

I might be wrong on my result. Is there a general formula for this?