Where are the values for B-Tree keys are stored?

user_4514838 0
Viewed 1012

I have been studying B-Trees for storing around 10k strings database each string having a unique id which I think can act as my key. But every implementation I seen, shows only keys in a B-Tree not the values. I am sure B-Tree when acting as map have to link values to keys but I cannot understand whether they stored within the node of tree along with a key. For Example. 

       ||key3|   |key6||
     /         |          \
    /   ||key4| |key5||    \
   /                        \
||key1| |key2||         ||key7| |key8||

       ||k3,v3| |k6,v6||
     /         |         \
    /   ||k4,v4||k5,v5||  \
   /                       \
||k1,v1| |k2,v2||         ||k7,v7| |k8,v8||

I am not sure how and where the values are stored.

b-tree tree hashmap data-structures
1 Answers

In every single node, both internal and leaf, along with keys.

In a B+-Tree, all keys are available in leaf nodes. So in case of splitting a leaf node, you can only push keys over to your parent, and keep values for yourself.In a B-tree, however, keys don't repeat, so you will have to have values in internal nodes.

You can use a Key-Value map and iterate over it's key for tree specific functions. Since you need to keep your keys sorted, you should use a sorted map, like TreeMap in java or simple std::map for c++. (Python doesn't have anything like that in standard library.) They also help in easily splitting a node and pushing things over to a new node.

user_45533090
Related