Blogspot supports HTTPS. Please always use it when linking to the site.
B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
51–60 of 78 posts
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#52Long ago, I was taking the sophomore level data structures and algorithms class. It was being transitioned from C to C++ and being taught by Professor DeWitt. I have vague memories of linked lists and then binary trees. ... And then we got to the spot where the syllabus from previous years had AVL trees and red black trees... and he scoffed at teaching it. And that I do remember. I suspect he had been doing lecture p…
I would not scoff at AVL trees. They are easy to prove correctness for, and admit a short implementation at ~100 lines. They're as short as AA trees, but AA trees are harder to prove with more cases. https://www.nayuki.io/res/aa-tree-set/BasicAvlTreeSet.java , https://www.nayuki.io/page/aa-tree-set
B-trees require a much longer implementation than AVL trees. https://www.nayuki.io/page/btree-set
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#53Earlier quoted context omitted.
Slightly random anecdote. Had an intern one summer at a large tech company I worked for, who was determined to inject a red-black tree in to the project they were working on for us, using hand-rolled code. I'm not sure what was going through his head at the time, whether he'd just learned how to write them at college, or if he just thought they were the pinnacle of engineering. None of the cases they were trying to s…
> I'm not sure what was going through his head at the time, whether he'd just learned how to write them at college, or if he just thought they were the pinnacle of engineering. I think it's easy to forget that a lot of interns might never have actually worked on a "real" codebase before; I know I certainly hadn't before my first internship! For someone who had only ever worked on homework code in classes before and m…
I remember part of it being that they beat efficiency into your brain throughout most of early CS. In college, using the naive approach is treated as being ignorant.
Then you work on real software and realize that computers are pretty fast and basic hashmaps & arrays will likely suffice for the size of the datasets you're working with, and beyond that, performance is more about tool/database choice than rolling your own algorithms.
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#54Earlier quoted context omitted.
> Later I looked at AVL trees... and they still give me a headache. Why? From what I remember AVL trees were much easier to implement than B-trees. Especially if using recursion.
Insertion in AVL tree's is fairly simple and doesn't really have any cascades so they are quite predictable, deletions on the other hand cascades upwards with a bunch of different imbalances and thus rotations(and post rotation balances) to be accounted for. Recently implemented them for an advanced hobby project and having a solid fuzzing tester in place really alleviated a lot of headaches in the long term since it…
B-tree deletions are quite complicated too, requiring stealing keys from either-side sibling or merging with either-side sibling.
In practice, I find that a B-tree implementation is 2 to 3× the length of an AVL tree impl.
I also fuzz-tested my implementations thoroughly. https://www.nayuki.io/page/avl-tree-list , https://www.nayuki.io/page/btree-set , etc.
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#55How B-trees can win is by taking advantage of the node children being sorted in an array. This allows a binary search to be used. A B-tree of any branching factor (not only 2) is equivalent to a binary tree. We can take any B-tree node n : n | ---------+----------- | | | | | | a b c d e f and regard it as an unbalanced tree n | / \ a /\ b/\ c/\ d/\ e/\ f nil When searching for an item, if we linearly search every nod…
Though, just spitballing here - I'd guess that, in practice, a linear search still tends to handily outperform a binary search (and, by extension, a well-balanced binary tree) whenever the keys are stored in a compact array. Due to better interaction with the cache and speculative execution.
yeah locality of reference is way better as you're traversing the array than as you follow links in the tree
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#56How B-trees can win is by taking advantage of the node children being sorted in an array. This allows a binary search to be used. A B-tree of any branching factor (not only 2) is equivalent to a binary tree. We can take any B-tree node n : n | ---------+----------- | | | | | | a b c d e f and regard it as an unbalanced tree n | / \ a /\ b/\ c/\ d/\ e/\ f nil When searching for an item, if we linearly search every nod…
Though, just spitballing here - I'd guess that, in practice, a linear search still tends to handily outperform a binary search (and, by extension, a well-balanced binary tree) whenever the keys are stored in a compact array. Due to better interaction with the cache and speculative execution.
Definitely depends on the branching factor! There are other encodings like Eytzinger that can provide further improves over "standard" binary search too [1].
[1] https://en.algorithmica.org/hpc/data-structures/binary-searc...
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#57How B-trees can win is by taking advantage of the node children being sorted in an array. This allows a binary search to be used. A B-tree of any branching factor (not only 2) is equivalent to a binary tree. We can take any B-tree node n : n | ---------+----------- | | | | | | a b c d e f and regard it as an unbalanced tree n | / \ a /\ b/\ c/\ d/\ e/\ f nil When searching for an item, if we linearly search every nod…
I think you might be missing the real performance characteristics of the hardware. The amount of comparisons might be the same, but comparisons are only a proxy for the expensive parts of lookups, the latency to tell RAM to provide data.
If the whole tree is in CPU cache then likely the difference is noise, but if the tree is large enough to have some data in RAM then the cost to copy that into cache will be larger based not on the size, but on the amount of queries from the CPU to the RAM (unless the size it way out of proportion). RAM has latency that is generally an order of magnitude slower than CPU Cache and generally an order of magnitude slower than fast contemporary storage.
There are many places you can find "Latency numbers every programmer needs to know" https://fullstackengineer.pro/blog/latency-numbers-programme...
But this trend has held for about 30 years and seem fundamental to the economics of building hardware. CPUs will be fastest, and cache slower, and RAM slower still , and fast storage still slower etc.
From your example, if it takes 100ns to get the node containing a~f then the whole of the B-Tree search for f might take 150ns (1 lookup from RAM + a few CPU intructions), but with the strictly binary tree it will need 6 lookups to RAM, and we can see that we can ignore the CPU time because it is so small. This could take 600ns (or 1300ns if each branch is a node with only pointers and the data needs to be dereferenced too). A smart cache prefetcher might guess that these were pointers and precache a and b once n was referenced, and might even cache things pointed to by loaded pointers but even in that highly optimistic scenario it could still take 300ns to load stuff.
Consider filesystems on storage and how they have had this problem but worse for a long time. Tree structures with many pointers are faster than binary trees in proportion to latency between the thing processing the tree and the place the tree it stored.
EDIT - And don't get me started on clever use of SIMD instruction. Imagine if node in a tree had binary layout matching an AVX register, then comparisons looking for the searched item could check a whole node in a single instruction! I am curious if there are any implementations that do this?
EDIT 2 - It does exist and I am late to the show, people have been doing this for like 15 years: https://stackoverflow.com/questions/20616605/using-simd-avx-...
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#58How B-trees can win is by taking advantage of the node children being sorted in an array. This allows a binary search to be used. A B-tree of any branching factor (not only 2) is equivalent to a binary tree. We can take any B-tree node n : n | ---------+----------- | | | | | | a b c d e f and regard it as an unbalanced tree n | / \ a /\ b/\ c/\ d/\ e/\ f nil When searching for an item, if we linearly search every nod…
I think you might be missing the real performance characteristics of the hardware. The amount of comparisons might be the same, but comparisons are only a proxy for the expensive parts of lookups, the latency to tell RAM to provide data. If the whole tree is in CPU cache then likely the difference is noise, but if the tree is large enough to have some data in RAM then the cost to copy that into cache will be larger b…
[deleted]
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#59How B-trees can win is by taking advantage of the node children being sorted in an array. This allows a binary search to be used. A B-tree of any branching factor (not only 2) is equivalent to a binary tree. We can take any B-tree node n : n | ---------+----------- | | | | | | a b c d e f and regard it as an unbalanced tree n | / \ a /\ b/\ c/\ d/\ e/\ f nil When searching for an item, if we linearly search every nod…
Though, just spitballing here - I'd guess that, in practice, a linear search still tends to handily outperform a binary search (and, by extension, a well-balanced binary tree) whenever the keys are stored in a compact array. Due to better interaction with the cache and speculative execution.
Suppose the key comparisons are much more expensive than the array or pointer navigation. Like the article does: it says that it is about theory, and it is looking at number of comparisons as the performance measure.
The fact that we can search a B-tree node that has, say, 256 children in 8 steps means that the node effectively contains the equivalent of a small balanced binary tree.
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#60I think either is a good choice for knowing nothing about the data set.
After n grows large enough, I think you’d want to benchmark your -exact- dataset on your -exact- prod hardware. Some datasets may cause certain trees to perform badly. Some hardware is much faster at memory lookups and cache misses are not as painful.
For instance, developing locally on Intel and deploying to Arm could yield pretty wild performance differences!