# return a key of a node with maximum value within a range of keys in B+ tree

I've been asked a question about B+ Tree.

The question is: Suppose we have object of the following type:

class Obj { private: int value; int key; public: Obj(int uniq_key , int value) }

and I am creating a Generic B+ tree which will sort objects in it leafs nodes by keys and not by values. (The keys are unique values aren't) Now I want to return the key of a node containes Maximum value within a range of keys. For Example:

If I have the following objects inserted in my B+ tree:

Obj a(1,10) , Obj(2,5) , Obj(3,0)

Then by calling this method I will get a return value : 1

I thought of having an extra rank tree with the same data stored in it and a pointer from a leaf node in the B+ tree to it's equivalent node in the rank tree but I think that there is a solution involves adding extra data in the nodes in the B+ tree which can solve this issue.

p.s. I don't know if this post is duplicated - I couldn't find anything else answering this kind of question.

Thank you, Michael

Now any range can be expressed as the union of $O(\log n)$ subtrees. In other words, you can find $O(\log n)$ nodes such that their descendants cover the range exactly. So, the max value of any node within that range can be obtained by looking at the values in those nodes, and taking the max of them. In this way each query can be answered in $O(\log n)$ time.
• @ms_stud, no, that doesn't sound like what I had in mind. I don't quite understand what you are suggesting but it doesn't seem to be what I had in mind. A first step for you: See if you can figure out why any consecutive range of leaves can be covered by a disjoint union of $O(\log n)$ subtrees. – D.W. Jan 2 '18 at 16:00