Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Btrees are the new black

me.net.nz

Post reply on HN
Print view View original

31–40 of 44 posts

Re: Btrees are the new black

#31

Post by ebiester »

bdg wrote: post #22

Someone should create a library where all your data is stored in a BTree. Think of it! Huge data sets, small data sets, everything scales in this system. And even better, they can create a language-agnostic API to a small server that just stores the btrees for them and gives them back on request. We could call it a database, but that would require we use indexes correctly for once in our lives.

And then we can stack every conceivable use case on top of it, and write that language-agnostic API in a way that makes interfacing with most current languages so onerous that people can build hundreds of thousands of lines of code to make it slightly less painful!

Maybe we can make the configuration so convoluted that we can base entire companies and revenue models around maintaining them.

Re: Btrees are the new black

#32

Post by yongjik »

alecco wrote: post #24
vinkelhake wrote: post #2

Google 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/

Funny how everything Google does is dogma. They move from complicated hash DS to B+trees, a decade later, and everyone follows. Better DS are currently Log-merge for heavy writes and data parallel BSTs for read-most. At least they are not stubborn for long, I give them that.

I don't know how you got that impression, but inside Google people use hash tables far, far more often than B+trees. In fact, I don't think I ever used B+tree once in my entire career inside Google.

It's pretty hard to beat "expected O(1)".

Re: Btrees are the new black

#33

Post by warmfuzzykitten »

jjh42 wrote: post #6
checker659 wrote: post #5

What about false sharing?

I only benchmarked and considered the single-threaded case. Multithreading is a whole new can of worms.

Trivially, one could synchronize around the entire tree.

However, if modified nodes are always copied, then the only node that matters is the root node (since there can never be a partially modified tree accessible from the root), which boils down to atomic update of a root node pointer. Should be very efficient.

There is, of course, a performance implication of node copying, but it only affects add/delete/replace performance - read access runs at full speed - and it is cache-friendly, as well.

Re: Btrees are the new black

#34

Post by anotherevan »

I have fond memories of red/black binary trees. About 15 years ago I wrote a reusable library for R/B trees in C. I had a series of programs I had to write that were collating a lot of data in memory into several buckets.

(The nice thing about virtual memory is you can make a really big RAM disk.)

Re: Btrees are the new black

#35

Post by justin66 »

JulienSchmidt wrote: post #15
joe_the_user wrote: post #4

Well, 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

There are even better fits for modern CPU architectures and hierarchical memory systems (but not on HDDs) than B-Tree based structures, like the adaptive radix tree: http://wwwkemper.informatik.tu-muenchen.de/~leis/papers/ART.... I think B-Trees are mostly important for educational purposes, since this is a very important general way of organizing data. For real world usage, there are hundreds of different structures…

Do you know of any examples of good open source projects using the ART?

Re: Btrees are the new black

#36

Post by coldtea »

ebiester wrote: post #31
bdg wrote: post #22

Someone should create a library where all your data is stored in a BTree. Think of it! Huge data sets, small data sets, everything scales in this system. And even better, they can create a language-agnostic API to a small server that just stores the btrees for them and gives them back on request. We could call it a database, but that would require we use indexes correctly for once in our lives.

And then we can stack every conceivable use case on top of it, and write that language-agnostic API in a way that makes interfacing with most current languages so onerous that people can build hundreds of thousands of lines of code to make it slightly less painful! Maybe we can make the configuration so convoluted that we can base entire companies and revenue models around maintaining them.

>write that language-agnostic API in a way that makes interfacing with most current languages so onerous that people can build hundreds of thousands of lines of code to make it slightly less painful

Those would be people who couldn't be bothered to learn a really simple declarative language, and prefer ad-hoc OO ORMS and other shit like that...

Re: Btrees are the new black

#37

Post by dkersten »

coldtea wrote: post #36
ebiester wrote: post #31

Earlier quoted context omitted.

And then we can stack every conceivable use case on top of it, and write that language-agnostic API in a way that makes interfacing with most current languages so onerous that people can build hundreds of thousands of lines of code to make it slightly less painful! Maybe we can make the configuration so convoluted that we can base entire companies and revenue models around maintaining them.

> write that language-agnostic API in a way that makes interfacing with most current languages so onerous that people can build hundreds of thousands of lines of code to make it slightly less painful Those would be people who couldn't be bothered to learn a really simple declarative language, and prefer ad-hoc OO ORMS and other shit like that...

SQL is not a simple language and expecting everyone to lean it properly is crazy. Simple queries are easy, sure, but as with all things you quickly outgrow simple things and then you're stuck. Especially if you want good performance.

Re: Btrees are the new black

#38

Post by thezorg »

Speaking of B-trees, I find CouchDB's implementation really interesting: the backing file is append-only, meaning that modifying the tree implies appending the modified nodes at the end of the file (for example, if I change a leaf, than I rewrite it at the end of the file, and rewrite its parent so that it points to the leaf's new position, and so on until we reach the root node).

Sounds like a waste of space, but it solves a bunch of problems, like being crash-proof (since we never overwrite anything, it's always possible to just find the last root) and allowing reads concurrent with a write without any synchronizing necessary. Plus, it's actually optimized for SSD's due to its log-like structure!

CouchDB B-Trees : http://guide.couchdb.org/draft/btree.html Log structures in SSDs : http://lwn.net/Articles/353411/

Re: Btrees are the new black

#39

Post by taeric »

dkersten wrote: post #37
coldtea wrote: post #36

Earlier quoted context omitted.

> write that language-agnostic API in a way that makes interfacing with most current languages so onerous that people can build hundreds of thousands of lines of code to make it slightly less painful Those would be people who couldn't be bothered to learn a really simple declarative language, and prefer ad-hoc OO ORMS and other shit like that...

SQL is not a simple language and expecting everyone to lean it properly is crazy. Simple queries are easy, sure, but as with all things you quickly outgrow simple things and then you're stuck. Especially if you want good performance.

SQL is arguably at least as easy as any other language you can define around this idea. Usually the complications come from trying to normalize the crap out of your data and expecting a single relational model to work for all use cases.

Oddly, moving this to another domain would not make things any easier in that regard. If you tried to have a single data structure that stores all of your data for all of your use cases, expect pain.

Re: Btrees are the new black

#40

Post by hyc_symas »

thezorg wrote: post #38

Speaking of B-trees, I find CouchDB's implementation really interesting: the backing file is append-only, meaning that modifying the tree implies appending the modified nodes at the end of the file (for example, if I change a leaf, than I rewrite it at the end of the file, and rewrite its parent so that it points to the leaf's new position, and so on until we reach the root node). Sounds like a waste of space, but it…

Massive waste of space though. LMDB is also copy-on-write and crash-proof but doesn't require compaction like CouchDB does.

http://symas.com/mdb/

Read the LDAPCon 2011 paper (and slides) to see how it works and why it's better than CouchDB.

Post reply on HN