rmind/masstree

Masstree -- lockless cache-aware trie of B+ trees [experimental]

masstree's Issues

A question about unstable state?

I see in your implementation, that unstable state is not a problem, because you put each key as deeper as possible, so each time there is key conflict you can inserting a new layer instead of replacing one.(Am i right?)
This is really clever! In this case key suffix is not needed and we don't have to retry when masstree_get, but at the cost of a bit more memory.

How do you come up with that?

I implement this algorithm lately, and I also did some modification, that new layer is created lazily, eg. a key with length 100 is store in layer 0 if there is no prefix conflict.

A question about keysuffixes

Hi:
Thanks for your masstree, it's cool.
I have a question about keysuffixes, my code is as follows:

tree = masstree_create(NULL);
char* key = "01234567AB";
char* key2 = "01234567XY";
masstree_put(tree, key, sizeof(key), (void *)1);
masstree_put(tree, key2, sizeof(key2), (void *)2);

I debug this and find key suffixes stored in layer 1, just like :

Layer 0              keyslice[0]: 01234567
                                 |
                               /  
Layer 1             keyslice[0]:AB         
                    keyslice[1]:XY

Layer 1 is leaf nodes in B+ tree, so, I think keyslice should store a complete key for range, and in paper, it has keysuffix_t keysuffixes, but I did not find in your code.

So, why store keysuffixes in keys-lice?