Given a B+ tree with M=3. We assume that the tree is static and it is not necessary to update the B+ tree. Also we know that all key-value pairs are stored in the leaves of the B+ tree. Internal nodes contain copies of keys stored in the leaves.
For simplicity we can assume that an internal node with d children holds d keys. The i-th key stored in the node u is the smallest key stored in the i-th child of u.
Now, we need to extend it to support given query named osearch(x,ef).
We are given a pointer to a leaf that holds the key $ef$ > $x$ and we search for the key $x$. Let $x−$ denote the largest key stored in the tree that is smaller than $x$. Let $df$ denote the number of elements between $x−$ and $ef$; if $x$ is smaller than all keys in the tree, then $df$ is the total number of keys that do not exceed $ef$.
Now we need an algorithm that answers queries osearch(x,f) in O(log $(df)$) time. That is, the time to answer a query osearch(x,f) must be logarithmic in the number of elements between ef and x−.
How to augment the B+ tree to answer this query ?