0

I need to implement a B+ tree which is adapted to be a k-d tree. As a short explanation of this, a k-d tree is like a binary tree except that at its nodes it has a multi-valued key, that is a key with several values. And it will also be a B+ tree cause the internal nodes are only meant to store 1 of the values of the key and the real data is stored at the leaf nodes. Here's a short graphical explanation of it:

short graphical explanation

My leaf nodes have space for 2 elements, when I add the first 2 everything works fine, till I add the third and I must make a split. For that, since I choose the first value of the key to be the one that defines the order, I take the median value of all three elements and the result is 27, so all elements less than 27 go to the left and those bigger or equal than go to the right.

When I add the 4th element, since Tom and Linda have age less than 27 they already completed a leaf node, son adding Dom makes the node to split again, but this time I must switch which value of the key defines the order which is Social Security Number. Again I take the median value and the result is 530, so all those with SS Number less than 530 go to the left, and so on.

Resulting with the final k-d tree, with certain values of the key as index in the internal nodes, and the complete key at the leaf nodes.

Now my question is, after explaining the context, how can I implement a solution for the keys, given that I do have to store at the leaf nodes the complete key, but at the internal nodes I only use one of the values of the key.

You can notice the resemblance with a database, where we have multiple fields with values, and we can sort the information with different fields at the same time, one more important than the next and so on.

I thought of making a class named Key or any other name, with atributes that hold all the values, for the above example, it could be int for age and int for SSNumber and string for name. But my problem is, what if my client decides he wants to add more values, then my class would grow bigger and bigger. Is this a good OO decision? Can I implement this another way and still be OO? I know my imagination can be poor, but since I can assume the client wants more values I could make some sort of list that holds my values, then it means I would have to make a list that can support any type of data, which doesn't sound like an OO approach. Any ideas?

Also I want to add that, since at some point of my algorithm of the tree ill need to take 1 attribute of the key to use as the index in the tree, I must support this as well.

I would really appreciate an idea of how to solve this by following an OO approach.

1 Answer 1

1

Make a Key an array of KeyPart, then each type of key value (age, ss#) can subclass from KeyPart. Then each internal node of your tree can store a single KeyPart and a key part index (to know what part it is the split of). The leaves can store the full Key.

2
  • This is WOW, awesome solution, thank you very much!!! Just 1 question, im not sure what you mean by "key part index" like a number that maps each subclass? Anyway i'm very confident now that i can work with this idea i can figure it out the rest. Again, thank you very much!
    – Ale
    May 6, 2012 at 17:49
  • Disregard my question about the key part index, i totally get it now. Your answer is just what i needed.
    – Ale
    May 6, 2012 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.