rmind / masstree Goto Github PK
View Code? Open in Web Editor NEWMasstree -- lockless cache-aware trie of B+ trees [experimental]
License: BSD 2-Clause "Simplified" License
Masstree -- lockless cache-aware trie of B+ trees [experimental]
License: BSD 2-Clause "Simplified" License
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?
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 declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.