# Augment B+ Tree to support given search query

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 ?

• Please use MathJax to disambiguate terms like "logdf". – Raphael Jun 15 '15 at 7:00
• @Raphael Edited – ms8 Jun 15 '15 at 7:40
• 1. I'm not clear on what the definition of osearch() is. What should osearch(x,f) return? You introduce all of this notation, but don't use it to define what osearch(x,f) should return. I don't see how we can answer the question, without this missing information. 2. What have you tried? What approaches did you consider? We expect you to make a significant effort before asking here, and to show us in the question what you tried. We want to help you understand concepts; just solving your exercise for you helps neither you nor anyone else. – D.W. Jun 16 '15 at 6:11