B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees • Hacker News Board

Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees

#61

Post by Twirrim » Mon, Jun 24, 2024, 6:29 PM UTC

saghm wrote: post #46

Twirrim wrote: post #37

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

First code reviews are always interesting with interns, I love reading through them to learn stuff (I'm an operations focussed / sysadmin type, coding is more something I've picked up as I've gone along and wanted to automate stuff)

This particular intern was dead set on this red-black tree, despite it being rejected constructively, repeatedly, every time they tried to introduce it, and despite mentoring on the subject from the experienced developer who was his mentor, and guidance from other engineers in the group.

The only intern I every had to deal with who didn't seem to recognise that production code is different from academic code, where the balance on clever vs maintainable is vastly different :)

Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees

#62

Post by globular-toast » Mon, Jun 24, 2024, 6:33 PM UTC

masklinn wrote: post #28

globular-toast wrote: post #19

Earlier quoted context omitted.

Not really. Hashmaps don't have guaranteed performance characteristics and require the "correct" hash function to work properly. In particular, their performance degrades as they become more "full" requiring a re-allocation to a table of generally n-times the size. Balanced trees could be regarded a more generic solution to the mapping problem and are more suitable in many applications.

> Not really. Yes really, that’s why the vast majority of languages default to a hashmap (if they even have tree-based maps at all). Turns out the average application is a lot more interested in a low-constant-factor O(1) best case than in a high-constant-factor O(log n) worst case. > Hashmaps don't have guaranteed performance characteristics Of course they do. > require the "correct" hash function to work properly.…

> Yes? Also “n-times” seems like pretty fuddy fud. And it seems weird to be more worried by the reallocation of a hashmap when a tree requires an allocation per node, so your average balanced tree requires a heap allocation per entry.

Yes, it requires allocation for every entry whereas a hash map requires it for some entries. You don't know which ones. So real time constraints are out the window. But no it's not something your average web programmer (including me) needs to worry about. Some people do, though.

Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees

#63

Post by harrison_clarke » Mon, Jun 24, 2024, 6:36 PM UTC

shagie wrote: post #2

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

red black trees can be thought of as 2-4 trees, and they're way less headache-inducing when you do

if you inline the red nodes into the black nodes, you get a 2-4 tree node. except that the 3-nodes have chirality. but then, you can just use a 2-4 tree

AVL trees seem not worth learning. they have slightly different performance characteristics than red-black trees. but, if i care about performance beyond big O, i'm probably using a hash table or a cache-aware tree of some kind instead of a CS101 data structure

Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees

#64

Post by kazinator » Mon, Jun 24, 2024, 7:07 PM UTC

sqeaky wrote: post #57

kazinator wrote: post #22

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

Like the article, I'm only concerned with comparison counts, trying to explain why B-trees look like balanced BSTs, and why that gets tighter and tighter with increasing numbers of children per node.

It's simply because the nodes themselves contain the equivalent of a balanced binary tree, in the form of a binary-searched array.

In the ultimate case, we set the number of children to be large enough to contain all the data, so then there is only one B-tree node, which is binary searched to find the element. Then we have the same number of comparisons as well balanced binary search tree.

Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees

#65

Post by kevin_thibedeau » Mon, Jun 24, 2024, 7:13 PM UTC

bunderbunder wrote: post #35

kazinator wrote: post #22

How 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.

It does. The break even point varies by platform but linear will win for sufficiently short arrays.

Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees

#66

Post by [deleted] » Mon, Jun 24, 2024, 7:22 PM UTC

sqeaky wrote: post #57

kazinator wrote: post #22

How 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

#67

Post by vlovich123 » Mon, Jun 24, 2024, 7:50 PM UTC

masklinn wrote: post #41

vlovich123 wrote: post #36

Earlier quoted context omitted.

From the looks of it Rust [1] uses a constant branching factor based on number of items whereas ABSEIL generally uses a target of 256 bytes [3] for branching and fits however many elements fit within that [2]. Rust’s approach seems to be more primitive as ABSEIL is optimizing for cache line usage (not sure why it’s several multiples of a cache line - maybe to help the prefetcher or to minimize cache line bouncing?) […

> not sure why it’s several multiples of a cache line - maybe to help the prefetcher or to minimize cache line bouncing? The AMD64 cache line is only 64 bytes, that would make for very low branching factors given interior nodes need a pointer per child, plus key, plus record pointer if b-tree (as opposed to b+tree).

To be clear, I was examining only leaf nodes. I’m not sure if interior nodes use the same logic. Still, ABSEIL generally uses a larger branching factor than Rust for some undocumented reason.

Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees

#68

Post by DanielHB » Mon, Jun 24, 2024, 7:50 PM UTC

nayuki wrote: post #54

whizzter wrote: post #49

Earlier quoted context omitted.

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.

Yeah, this is what I was thinking too. The rebalancing on AVL is a bit tricky but once you grok it, it is not that much code...

Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees

#69

Post by 9659 » Mon, Jun 24, 2024, 9:34 PM UTC

sqeaky wrote: post #57

kazinator wrote: post #22

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

Just because it was first discovered 15 years ago, does not mean it wasn't still a good idea.

Keep on thinking. You never know what else you will come up with.

Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees

#70

Post by torginus » Mon, Jun 24, 2024, 9:41 PM UTC

bunderbunder wrote: post #35

kazinator wrote: post #22

How 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.

I remember reading a blogpost about this, they compared binary search on integer keys with a highly-optimized unrolled SIMD linear search.

The takeaway was that the break-even point was suprising small - just tens of elements, which is crazy considering a CPU can do like 2x 8-wide AVX2 integer comparisons in a single cycle. Modern CPUs are just that good at executing branchy code.

But with B-trees we can have the best of both worlds - trees with a relatively high branch factor, like 16, that can still be tested in one go using SIMD.

Another advantage is cache locality - which is one of the reasons B-trees are favored when implementing filesystems - much of the tree doesn't need to be fetched into memory while the parts that do are contiguous in memory.