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

41–50 of 78 posts

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

#41

Post by masklinn »

vlovich123 wrote: post #36
leni536 wrote: post #18

Earlier quoted context omitted.

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

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

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

#42

Post by ajuc »

teruakohatu wrote: post #4
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…

I feel there must be better ways of learning the principles of algorithms than balancing trees. I suffered through RB trees.

Suffering is the point. It's like exercises in math or push-ups - if you find a way to do them effortlessly you won't develop the skills you are training for.

I agree they suck tho.

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

#43

Post by aidenn0 »

cperciva wrote: post #5

In a sense, red-black and 2-3 trees are just a special case of B-trees with small nodes. Smaller B-tree nodes have (by a constant factor) more expensive searching than larger nodes; but smaller nodes are more efficient for mutating operations. And indeed, if you have an insert/delete heavy workload you can't beat something like a red-black tree.

AA trees are isomorphic to 2,3 trees and RB trees are isomorphic to 2,4 trees. IIRC we learned 2,4 trees first in my data-structures class, and then demonstrated that RB trees were a different representation of the same idea.

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

#44

Post by shagie »

prerok wrote: post #39
shagie wrote: post #31

Earlier quoted context omitted.

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

Having a class in databases from the person who was the DeWitt Clause in Oracle licenses.

I had his class before (the aforementioned sophomore data structures and algorithms) and I knew he was a good lecturer. That wasn't a question. It was a "too much going on that semester and I wasn't able to do the assignments in a timely manner".

Professor Landweber's class had a waiting list that I scoffed at as a college student and looked for something that I could get into and fill the requirement without realizing who he was. It wasn't until later while reading the UNIX and Linux System Administration Handbook and seeing an image in there that was attributed to him that the name clicked but he wasn't teaching that next semester and I had filled that requirement elseclass.

Another regret was dropping numerical methods with Professor de Boor ( https://en.wikipedia.org/wiki/Carl_R._de_Boor ) when I couldn't get my head around splines rather than going to his office hours (he was also the undergraduate advisor and very helpful).

Those classes could have changed the trajectory of my career. I was looking at being a sysadmin instead and writing perl and keeping some big iron running. My career pivoted from sysadmin to webmaster to web developer (perl) to web developer (Java). I have no regrets from that path - I do have regret for not learning what I could from the experts in their field when I was in a place and time to learn from them.

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

#45

Post by rdtsc »

Twirrim wrote: post #37
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…

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.

That's understandable and rather common with new fresh grads. They have the energy and motivation but may not quite have the experience. We were all there once, including me.

My history professor from 8th grade used say: "There is a difference between knowing what you're doing and doing what you know".

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

#46

Post by saghm »

Twirrim wrote: post #37
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…

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 maybe some side projects for fun, it's very easy to imagine that they honestly didn't understand that implementing the hardest data structure they knew by hand wouldn't actually be an impressive display of engineering to the company they were hoping to get a job offer from.

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

#47

Post by saghm »

kristopolous wrote: post #14
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…

Honestly for me it's either linear search, dictionary, or external store like database and that's actually it. I think I've had to implement my own traversable data structure literally only in interviews

To clarify, I definitely don't mean I've been implementing these structures by hand! Even when using data structures from the standard library or other dependencies though, I just don't end up needing sort-ordered collections very often in my work, and I thought that was interesting (although sibling comments might indicate that this isn't necessarily typical).

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

#48

Post by sqeaky »

globular-toast wrote: post #27
fanf2 wrote: post #25

Earlier quoted context omitted.

Trees require a lot more memory indirections than hashmaps, which makes them slower to traverse. They require a lot more interior pointers, which makes them bigger. It’s easy for a hashmap to beat a tree.

Not in the worst case.

Which will be the developers responsibility to know when that is and is rarely the default or normal case.

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

#49

Post by whizzter »

DanielHB wrote: post #26
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…

> 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 was able to produce quite an exhaustive set of conditions.

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

#50

Post by saghm »

masklinn wrote: post #16
globular-toast wrote: post #12

Earlier quoted context omitted.

They're not about maintaining sort order, though? They're about arbitrary lookup. Or do you mean "if I had to pick one nice side effect"?

If your concern is just arbitrary lookups then your baseline is a hashmap though.

Yep, this is the thought process I had; a red-black tree or B-tree is something I'd consider for a map that needed sort order, and a hashmap would be what I'd use by default if I didn't care about order.

For additional context, I work almost entirely in Rust nowadays, and BTreeMap and HashMap are the two map types in the standard library (https://doc.rust-lang.org/std/collections/index.html). I've ended up needing insertion-ordered maps quite often in my work though, which is not something I've seen taught very often or in standard libraries, although there are plenty of third-party implementations out there, and in most languages it's not too difficult to hand-roll an implementation using an unordered map and a linked list by keeping both the value and a reference to the node containing the element in the map, which provides constant time insertion, lookup and deletion. (Rust is somewhat notorious for _not_ being a language where implementing something like this by hand is super easy though, since tracking mutable references to individual nodes of a linked list across separate hashmap values is not something the borrow checker is enthusiastic about)

Post reply on HN