Btrees are the new black
me.net.nz
Btrees are the new black
1–10 of 44 posts
Re: Btrees are the new black
#2Google has an open source implementation of b-trees in C++. You gain performance and memory efficiency (less overhead per element stored). You lose the iterator stability that std::map/std::set guarantees. Other than that the interfaces are pretty much equal.
Re: Btrees are the new black
#3Google has an open source implementation of b-trees in C++. You gain performance and memory efficiency (less overhead per element stored). You lose the iterator stability that std::map/std::set guarantees. Other than that the interfaces are pretty much equal. https://code.google.com/p/cpp-btree/
(top article author). I wasn't aware of that, it looks like they come to similar conclusions "B-trees are widely known as data structures for secondary storage, because they keep disk seeks to a minimum. For an in-memory data structure, the same property yields a performance boost by keeping cache-line misses to a minimum. C++ B-tree containers make better use of the cache by performing multiple key-comparisons per node when searching the tree. Although B-tree algorithms are more complex, compared with the Red-Black tree algorithms, the improvement in cache behavior may account for a significant speedup in accessing large containers."
Re: Btrees are the new black
#4Well,
If the hype is to be believed, Cache-oblivious b-trees are an even better match for today's hierarchical memory systems.
Unfortunately, I don't know any simple free/open-source implementation of these.
But here is a "home page" for them: http://supertech.csail.mit.edu/cacheObliviousBTree.html
Re: Btrees are the new black
#5What about false sharing?
Re: Btrees are the new black
#6What about false sharing?
I only benchmarked and considered the single-threaded case. Multithreading is a whole new can of worms.
Re: Btrees are the new black
#7Interestingly, a red-black tree can be viewed as a BTree [0].
Another case where caching plays a huge role in determining the most efficient data structure (See vector vs list [1]).
[0]: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Analogy_...
[1]: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector...
Re: Btrees are the new black
#8Well, If the hype is to be believed, Cache-oblivious b-trees are an even better match for today's hierarchical memory systems. Unfortunately, I don't know any simple free/open-source implementation of these. But here is a "home page" for them: http://supertech.csail.mit.edu/cacheObliviousBTree.html
[deleted]
Re: Btrees are the new black
#9Google has an open source implementation of b-trees in C++. You gain performance and memory efficiency (less overhead per element stored). You lose the iterator stability that std::map/std::set guarantees. Other than that the interfaces are pretty much equal. https://code.google.com/p/cpp-btree/
(top article author). I wasn't aware of that, it looks like they come to similar conclusions "B-trees are widely known as data structures for secondary storage, because they keep disk seeks to a minimum. For an in-memory data structure, the same property yields a performance boost by keeping cache-line misses to a minimum. C++ B-tree containers make better use of the cache by performing multiple key-comparisons per n…
A sidenote: your blog post is from the future - unless we're already in May? :)
Re: Btrees are the new black
#10Earlier quoted context omitted.
(top article author). I wasn't aware of that, it looks like they come to similar conclusions "B-trees are widely known as data structures for secondary storage, because they keep disk seeks to a minimum. For an in-memory data structure, the same property yields a performance boost by keeping cache-line misses to a minimum. C++ B-tree containers make better use of the cache by performing multiple key-comparisons per n…
A sidenote: your blog post is from the future - unless we're already in May? :)
Fixed. I'd like to say it was a subtle implication that it contains wisdom from the future ... but actually it was just me being boneheaded.