B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
databasearchitects.blogspot.com
B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
1–10 of 78 posts
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#2Long 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 planning over the weekend (this was in the "we're redoing the class, teach it as it needs to be taught" type mandate) and he had us skip that section of the text. The fist lecture he was going off of overhead transparencies that he was writing as he lectured. The second lecture he gave us photocopies of hand written notes and diagrams.
Instead of AVL and red black trees, we instead learned about 2-3 trees and B trees.
For what it's worth, I still know how to do 2-3 trees from scratch.
Later I looked at AVL trees... and they still give me a headache.
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#3Long 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 use to make me anxious. I think the first time I grasped them was after watching Erik Demaine's lecture on the topic. For anyone interested it is this [1]; its still a very good reference on the topic!
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#4Long 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.
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#5In 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.
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#6Long 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…
B-trees are definitely more useful, but I don’t think they’re really a good idea to start out with as your first balanced tree.
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#7In 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.
This sounds surprising, unless you mean specifically a workload where a bunch of inserts and deletes are made using a stored cursor, so that they don't need to follow a bunch of pointers from the root.
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#8Long 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.
There are two fundamental things to teach in an algorithms course:
1) that there are many programs that implement the same algorithm, and many algorithms that implement the same function.
2) that there are a few basic tradeoffs we can make when implementing a function/customising an algorithm: space vs time, read vs write, deterministic vs indeterministic, etc.
I'd guess trees have traditionally been used, because there's a whole zoo of them, which clearly presents (1) and allows (2) to be learned (in "cookbook" style) even if they're never explicitly presented (in "textbook" style).
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#9Long 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 reason, I've run into cases far more often where I need to maintain insertion order than sort order, but I'm not confident about whether this is due more to the type of stuff I work on or if it's just a more common requirement in general.
Re: B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
#10Long 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.