Let’s Invent B(+)-Trees
shachaf.net
Let’s Invent B(+)-Trees
1–10 of 72 posts
Re: Let’s Invent B(+)-Trees
#2Interesting. :-)
I recently posted a brief document I wrote about a similar structure, immutable AVL trees. I find AVL trees a very nifty structure, I think they don't get as much credits as they deserve: logn (which in practice is about the same as "constant" for most values of n one encounters in practice) insertion, lookup, deletion and even append (for position-based trees, with some assumptions). Incredibly simple implementation. And, if immutable (based on shared memory), allows trivial snapshotting, having multiple "concurrent" trees sharing most of their memory.
Anyhow, it's here: https://github.com/alefore/weblog/blob/master/immutable-avl-...
I have a small implementation here (which I use, among other things, to hold all lines in a file, in my text editor): https://github.com/alefore/edge/blob/master/src/const_tree.h
Re: Let’s Invent B(+)-Trees
#3Uhh ... why is this the top article on HN? I know all about B-trees, and I do not understand what is new or interesting in this very brief page.
Re: Let’s Invent B(+)-Trees
#4Uhh ... why is this the top article on HN? I know all about B-trees, and I do not understand what is new or interesting in this very brief page.
The exposition is tight.
Re: Let’s Invent B(+)-Trees
#5[deleted]
Re: Let’s Invent B(+)-Trees
#6Interesting. :-) I recently posted a brief document I wrote about a similar structure, immutable AVL trees. I find AVL trees a very nifty structure, I think they don't get as much credits as they deserve: logn (which in practice is about the same as "constant" for most values of n one encounters in practice) insertion, lookup, deletion and even append (for position-based trees, with some assumptions). Incredibly simp…
All node-based trees with a small branching factor of 2-3 have the same performance problems on modern hardware, irrespective of the theoretical big-O algorithmic complexity.
They all have poor memory locality, high overheads, and high indirection. This is kryptonite for typical x86 or ARM CPUs. Unless you're only developing for some tiny embedded CPU with no cache, no branch predictor, and low frequency, such algorithms belong in the dustbin of history.
Practically always, you get better actual performance when using array-based structures such as hashtables, B-Trees, or the like.
Features like snapshotting can be implemented using virtual memory tricks, but is a gimmick rarely used outside of pure functional languages. You might find that simply copying an array when needed for a snapshot is faster than a fancy tree with sharing as a native capability. The exception would be certain dynamic programming scenarios where cloning is very common.
Re: Let’s Invent B(+)-Trees
#7Uhh ... why is this the top article on HN? I know all about B-trees, and I do not understand what is new or interesting in this very brief page.
Your knowledge isn't mine -- I found this to be quite a condensed way to understand something I've little relation to.
What do you have to contribute that teaches not criticises?
Re: Let’s Invent B(+)-Trees
#8Interesting. :-) I recently posted a brief document I wrote about a similar structure, immutable AVL trees. I find AVL trees a very nifty structure, I think they don't get as much credits as they deserve: logn (which in practice is about the same as "constant" for most values of n one encounters in practice) insertion, lookup, deletion and even append (for position-based trees, with some assumptions). Incredibly simp…
I don't know about you, but when I started learning data structures, my professor told me AVL trees lost the popularity battle with red-black trees, and people tended to use red-black trees more. He didn't mention AVL trees besides a footnote. Nowadays even red-black trees aren't favored due to practical concerns like caches, so I assume AVL trees are very niche.
Re: Let’s Invent B(+)-Trees
#9Interesting. :-) I recently posted a brief document I wrote about a similar structure, immutable AVL trees. I find AVL trees a very nifty structure, I think they don't get as much credits as they deserve: logn (which in practice is about the same as "constant" for most values of n one encounters in practice) insertion, lookup, deletion and even append (for position-based trees, with some assumptions). Incredibly simp…
I don't know about you, but when I started learning data structures, my professor told me AVL trees lost the popularity battle with red-black trees, and people tended to use red-black trees more. He didn't mention AVL trees besides a footnote. Nowadays even red-black trees aren't favored due to practical concerns like caches, so I assume AVL trees are very niche.
> Nowadays even red-black trees aren't favored due to practical concerns like caches
Not sure if that's true. In addition to the main linux trunk using them, Java 8 included them also as an improvement to their HashMap (I found this by googling), so I don't they are not favored anymore.
Edit: language.
Re: Let’s Invent B(+)-Trees
#10That made sense. I was following along, and then all of a sudden, it just kind of ended.
As a layman who doesn't clearly remember B Trees, it would be awesome to have even a sentence at the end, like
...and that's B Trees! Commonly used for storing fields in relational databases, filesystems, and more!
For fellow laymen, https://en.wikipedia.org/wiki/B-tree isn't bad, but is there more?