Very... Short article. Anyway my favorite kind of tree is the R tree if you want to go down the research rabbit hole.
Let’s Invent B(+)-Trees
11–20 of 72 posts
Re: Let’s Invent B(+)-Trees
#12That 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?
The Postgres documentation on btrees is absolutely stellar if you can afford some extended time to study it [1]. From there you can read the actual code or watch some videos on how Postgresql indexes use them. You can even dump indexes locally to see their content! from root all the way to the leaf nodes [2] (this assuming you read and understood the above).
[1] https://github.com/postgres/postgres/tree/master/src/backend...
Re: Let’s Invent B(+)-Trees
#13This sounds exactly how the excellent Python Sorted Containers library works, and achieves "faster than C" performance in pure Python by effective use of the bisect module (which itself is written in C). http://www.grantjenks.com/docs/sortedcontainers/implementati...
> The Sorted Containers internal implementation is based on a couple observations. The first is that Python’s list is fast, really fast. Lists have great characteristics for memory management and random access. The second is that bisect.insort is fast. This is somewhat counter-intuitive since it involves shifting a series of items in a list. But modern processors do this really well. A lot of time has been spent optimizing mem-copy/mem-move-like operations both in hardware and software.
> But using only one list and bisect.insort would produce sluggish behavior for lengths exceeding ten thousand. So the implementation of Sorted List uses a list of lists to store elements. In this way, inserting or deleting is most often performed on a short list. Only rarely does a new list need to be added or deleted.
> Sorted List maintains three internal variables: _lists, _maxes, and _index. The first is simply the list of lists, each member is a sorted sublist of elements. The second contains the maximum element in each of the sublists. This is used for fast binary-search. The last maintains a tree of pair-wise sums of the lengths of the lists.
Re: Let’s Invent B(+)-Trees
#14Interesting. :-) 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 algori…
Thank you for your reply. Interesting points.
I guess I'll implement an analogous immutable B-Tree structure and run some benchmarks. I suspect you're probably right. I'll probably experiment with different branching factors and tree sizes.
I rely a lot on the trivial (i.e., zero cost) snapshotting for feeding work to background threads. For my workload, having to do deep copies constantly would be prohibitively expensive (and I'd rather not deal with the complexity of explicit locking). That said, I'm now curious to see whether using immutable B-Trees will yield significantly better performance. I suspect they likely will. Exciting. :-)
Thanks again!
Re: Let’s Invent B(+)-Trees
#15Earlier quoted context omitted.
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.
There are cases where you need them, but it's relatively rare, they definitely shouldn't be your first choice.
I'm fuzzy on all the current Linux use cases, but do remember one of the main users of rb trees was CFS. It's a neat scheduling algorithm.
Java 8 specifically: HashMap is implemented with linked list chaining. This is already not very performant, but you can only do so much with Java being a reference heavy language. RB trees are used if the bucket chain grows excessively long - so it's addressing an edge case, speeding up some worst case scenarios.
Dense hash tables based on open addressing outperform bucketed chaining. Look also at abseil's swiss table or folly's f14 if you want to see how they've further advanced to take advantage of the hardware.
In general: flat, dense, linear structures are king for performance.
Re: Let’s Invent B(+)-Trees
#16Interesting. :-) 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 algori…
The traditional ZFS implementation(s) use AVL trees as the in-memory data structure for allocating space (ie finding free disk space).
However the performance limitations of them have started to show, so there's been work done to switch to B-trees[1].
Re: Let’s Invent B(+)-Trees
#17Interesting. :-) 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…
Thanks for sharing! I don’t remember C++ well at all anymore, but it’s cool to see an immutable AVL tree in it since it seems like it would be less common. I wrote one in F# a while back for fun/curiosity since I had no idea how it would be done at the time. Mine was purely key based though. The indexing idea is neat too!
Re: Let’s Invent B(+)-Trees
#18I love the idea but I'd love to see someone implement this and then show performance and memory comparisons to trees and normal arrays.
Re: Let’s Invent B(+)-Trees
#19I'm somewhat ignorant of theory but when I ran into this I just kept a separate unsorted array of values to-be added. In moments of idleness the extra array is sorted and if time allows it the entire thing is sorted into the original.
Also a fun approach for an array of sorted numbers is to use bits and have the offset represent the value.
Re: Let’s Invent B(+)-Trees
#20I published a reference implementation of B-trees that is optimized for clarity and conciseness: https://www.nayuki.io/res/btree-set/btreeset.py ; https://www.nayuki.io/page/btree-set