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

21–30 of 44 posts

Re: Btrees are the new black

#21

Post by srean »

kerneis wrote: post #19
srean wrote: post #16

Since there has been a resurgence of interest in OCaml on HN, some may be curious to see how a production quality Btree implementation looks like in OCaml. Algebraic data types, make it particularly convenient for these sorts of things. For comparison one may contrast it with an implementation in a language that does not have algebraic types, C++ for example. So glad Rust chose to have them. Here is a Btree implement…

> Here is a Btree implementation from the mirage project And in fact, this implementation does not show a lot because the actual B-tree work is done by the baardskeerder library: https://github.com/Incubaid/baardskeerder It looks very large and complex, it is most certainly possible to write a simpler, pedagogical implementation.

Found cpc https://github.com/kerneis/cpc from your comment stream. Looks super interesting. http://felix-lang.org/share/src/web/tut/fibres_index.fdoc might pique your interest. It also compiles coroutines portably and efficiently (to a C++ runtime library). Felix tries to do for C++ what F# does to C# (in case there is any confusion, I am just a new user)

Re: Btrees are the new black

#22

Post by bdg »

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.

Re: Btrees are the new black

#23

Post by thesz »

jjh42 wrote: post #3
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/

(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…

BTrees are cache-aware, and, in a sense, cache-oblivious.

There are more interesting structures, like fractal tree indices, which are cache-oblivios in the very formal sense.

My own opinion is that Btrees are nice, but not very effective in current world. Structures like LSM trees can be more effective. And you can construct high efficiency search structures over runs of LSM tree which will mimic Btrees.

Re: Btrees are the new black

#24

Post by alecco »

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.

Re: Btrees are the new black

#25

Post by rplnt »

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.

NTFS uses BTrees I believe. And matches your requirements.

Re: Btrees are the new black

#26

Post by taeric »

rplnt wrote: post #25
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.

NTFS uses BTrees I believe. And matches your requirements.

Mayhap I'm the one missing the joke. That being that this is just describing databases, period.

Re: Btrees are the new black

#27

Post by [deleted] »

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.

[deleted]

Re: Btrees are the new black

#28

Post by erichocean »

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.

If you do want a B-tree library in C that's not tied to SQL, I've had good success with lmdb[0]. As a bonus, it's also transactional and writers do not block readers (and vice versa). Crazy fast and easier to use from C than SQLite IMO.

If you want B-trees that compete with LSM trees, stratified B-trees[1] are pretty sweet. There's an in-kernel GPL implementation called Castle[2] on GitHub.

[0] http://symas.com/mdb/

[1] http://www.slideshare.net/acunu/20110620-stratifiedbtree

[2] https://github.com/acunu/castle

Re: Btrees are the new black

#30

Post by jjh42 »

briandw wrote: post #29

Under what conditions will a B-tree out perform a hash map? Seems like the hash map was far and away the better choice in his test.

For insertions and lookup it is probably hard to find a situation (for large n hashes are asymptotically superior).

Trees provide some other nice properties such as maintaining an ordering (so it's fast to get the smallest argument or interate of the elements in numerical order) and always perform at the asymptotic time cost (a dynamic hash table occasionally takes O(n) when the table is resized so it might not be a good fit in a realtime situation)

Post reply on HN