Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees

databasearchitects.blogspot.com

Post reply on HN
Print view View original

31–40 of 78 posts

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

#31

Post by shagie »

saghm wrote: post #9
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…

> Instead of AVL and red black trees, we instead learned about 2-3 trees and B trees When we first were taught about B trees in my databases course in college, he professor quipped something like "these are the reason you'll never actually use a red-black tree in practice". I've actually found that in practice I rarely ever up actually needing to use any sort of data structure that maintains sort order; for whatever…

> When we first were taught about B trees in my databases course in college

I'll note that the instructor for this was Professor David DeWitt - https://en.wikipedia.org/wiki/David_DeWitt

He normally taught databases and one of my great regrets was dropping his 500 level database class one semester when things were rough. (Another regret was not taking networking from Professor Landweber https://en.wikipedia.org/wiki/Lawrence_Landweber .)

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

#32

Post by lrschaeffer »

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

>> Hashmaps don't have guaranteed performance characteristics

>Of course they do

No, they do not, at least not worst case O(1). If you write a very poor (but functional!) hash function or an adversary is choosing your items, then congratulations, your hashmap is now a linked list with extra steps.

Sure, you could use a robust cryptographic hash function, but you didn't because (a) it's not the default in your language and (b) it's slow and you are "a lot more interested in a low-constant-factor O(1) best case".

Otherwise, you're more or less correct.

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

#33

Post by Maxatar »

lrschaeffer wrote: post #32
masklinn wrote: post #28

Earlier quoted context omitted.

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

>> Hashmaps don't have guaranteed performance characteristics >Of course they do No, they do not, at least not worst case O(1). If you write a very poor (but functional!) hash function or an adversary is choosing your items, then congratulations, your hashmap is now a linked list with extra steps. Sure, you could use a robust cryptographic hash function, but you didn't because (a) it's not the default in your languag…

I mean it's kind of pedantic but yes hash maps do have guaranteed performance characteristics. They are not guaranteed to be O(1), but they will never be something like O(2^N) either. You can give guarantees about their performance if you can make guarantees about the distribution of the inputs and the properties of the hash used.

In my own experience, most uses of hash maps are typically O(logn). A good rule of thumb is hash maps are preferable unless you need predictable worst case performance or your hash maps are directly exposed to the public.

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

#34

Post by jvanderbot »

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 don't think so?

I think the b-tree is using the start/end sequence knowledge at each to do fewer node evaluations. That is, a b-tree is "shorter" so of course it'll take fewer node evaluations to reach the leaf.

"b-tree is equivalent to balanced binary tree", and "unbalanced tree", don't make a ton of sense when ostensibly the article compares b-trees to balanced BST.

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

#35

Post by bunderbunder »

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.

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

#36

Post by vlovich123 »

leni536 wrote: post #18
masklinn wrote: post #11

> Practical B-trees often use fairly large values of k (e.g., 100) and therefore offer tight bounds -- in addition to being more cache-friendly than binary search trees. That is true on-disk, where you would not use BSTs anyway. In-memory, mid to high single digit values are practical. For instance iirc Rust’s btree (map and set) uses something like k=6.

Interesting, Abseil's btree claims to use a larger value: ... for absl::btree_set , nodes currently have 62 children ... https://abseil.io/about/design/btree

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?)

[1] https://github.com/rust-lang/rust/blob/master/library/alloc/...

[2] https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724...

[3] https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724...

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

#37

Post by Twirrim »

saghm wrote: post #9
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…

> Instead of AVL and red black trees, we instead learned about 2-3 trees and B trees When we first were taught about B trees in my databases course in college, he professor quipped something like "these are the reason you'll never actually use a red-black tree in practice". I've actually found that in practice I rarely ever up actually needing to use any sort of data structure that maintains sort order; for whatever…

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 shoe-horn them in to made sense. Places where you might debate that even a straight array would be sufficient, due to the limited number of items. The worst case of searching to the end of the array wouldn't matter. Doubly so given they weren't working on anything anywhere near a hot path, or a time sensitive operation. Standard library components would have been perfectly fine, and not carried the maintenance burden.

They did, on at least a couple of occasions, smugly explain what a black-red tree was to their mentor, who had likely implemented their first red-black tree at college before that Intern had ever even touched a computer for the first time. He showed remarkable patience.

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

#38

Post by masklinn »

Maxatar wrote: post #33
lrschaeffer wrote: post #32

Earlier quoted context omitted.

>> Hashmaps don't have guaranteed performance characteristics >Of course they do No, they do not, at least not worst case O(1). If you write a very poor (but functional!) hash function or an adversary is choosing your items, then congratulations, your hashmap is now a linked list with extra steps. Sure, you could use a robust cryptographic hash function, but you didn't because (a) it's not the default in your languag…

I mean it's kind of pedantic but yes hash maps do have guaranteed performance characteristics. They are not guaranteed to be O(1), but they will never be something like O(2^N) either. You can give guarantees about their performance if you can make guarantees about the distribution of the inputs and the properties of the hash used. In my own experience, most uses of hash maps are typically O(logn). A good rule of thum…

> A good rule of thumb is hash maps are preferable unless you need predictable worst case performance or your hash maps are directly exposed to the public.

Also, obviously, features only one of them provides e.g. if you need range queries then a hash table is quite useless. Meanwhile if you need insertion ordering, that’s reasonably easy to do with a hashmap.

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

#39

Post by prerok »

shagie wrote: post #31
saghm wrote: post #9

Earlier quoted context omitted.

> Instead of AVL and red black trees, we instead learned about 2-3 trees and B trees When we first were taught about B trees in my databases course in college, he professor quipped something like "these are the reason you'll never actually use a red-black tree in practice". I've actually found that in practice I rarely ever up actually needing to use any sort of data structure that maintains sort order; for whatever…

> When we first were taught about B trees in my databases course in college I'll note that the instructor for this was Professor David DeWitt - https://en.wikipedia.org/wiki/David_DeWitt He normally taught databases and one of my great regrets was dropping his 500 level database class one semester when things were rough. (Another regret was not taking networking from Professor Landweber https://en.wikipedia.org/wiki/…

May I ask why you regret it?

It could be that my professors were simply not that good, so that I don't really understand this. I mostly groked the subjects by working through the books and exercises in them. The professors' lectures almost always went over some detail too quickly, so in a 3 hour lecture, I usually ended up following only the first hour or so.

My question is maybe better put as: what quality or approach makes them great lecturers?

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

#40

Post by skribanto »

29athrowaway wrote: post #10
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…

Left leaning red black trees are simpler to implement than the regular red black tree.

Left leaning red black trees enforce extra constraints, which remove symmetries. This actually adds an edge case when instead you can just treat left/right rotations and comparisons as symmetric operations.

Left Leaning Red Black Trees Considerer Harmful: https://www.read.seas.harvard.edu/~kohler/notes/llrb.html

Post reply on HN