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

11–20 of 44 posts

Re: Btrees are the new black

#11

Post by nonsens3 »

cheepin wrote: post #7

Interestingly, 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...

Robert Sedgewick gives a very good analogy of a red-black tree to a 2-3 tree on his Coursera course (Algorithms, Part I) [0] - a bit different to what is discussed in Wikipedia, but very easy to understand and implement.

[0]: https://class.coursera.org/algs4partI-004

Re: Btrees are the new black

#14

Post by beagle3 »

The original B-Trees as described by Bayer were "intrusive" (like implemented here), in the sense that every node contains keys, values, and pointers.

There are variants such as the B+Tree http://en.wikipedia.org/wiki/B%2B_tree , which stores only keys in nodes and chains blocks - which is more efficient in range scans and less in general retrieval; And the http://en.wikipedia.org/wiki/B*-tree which is more densely packed.

Re: Btrees are the new black

#15

Post by JulienSchmidt »

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 optimized for different use cases.

Re: Btrees are the new black

#16

Post by srean »

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 implementation from the mirage project [1] https://github.com/cgreenhalgh/ocaml-btree/blob/master/lib/b...

EDIT: removed link to binary tree after kerneis pointed it out.

[1] http://www.openmirage.org/

Re: Btrees are the new black

#17

Post by narag »

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…

Sweet. I remember writing an implementation in TurboPascal in the nineties. This is... refreshing :-)

Re: Btrees are the new black

#18

Post by kerneis »

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…

> It can be shorter still, if all you want is insert and read

Despite the name, I'm afraid this is a simple binary tree implementation, not a BTree:

type 'a tree = Empty | Node of('a * 'a tree * 'a tree);;

Obviously the author didn't know what he was doing (the intended scope was very large, AVL, BTrees, etc. but he stopped after committing this single file).

Re: Btrees are the new black

#19

Post by kerneis »

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.

Post reply on HN