News for hackers. Stuff that matters.
Re:Left-leaning red-black trees are hard to implement (2008) by adrianN on Monday December 01, 2014 @03:14AM (#8679976)
This seems to confirm my hunch that there is no reason to use anything but b-trees on modern computers, at least for single threaded code. Storing more values in the nodes and increasing the branching factor is better because you do more of your work inside the cache and avoid random memory access.

I also find b-trees much simpler to implement than either RB or AVL trees.

Re:Left-leaning red-black trees are hard to implement (2008) by kcl on Monday December 01, 2014 @01:52PM (#8682879)
I stop short of recommending B-trees as the only tree structure you need to know. I think if it matters at all what kind of tree you're using, you're deep enough in the guts that it pays to know the differences between B-trees and basic trees.

To me, this is especially relevant today, since if you need a "B-tree", you probably need a standard relational database (MySQL/PostgreSQL/SQLite), and if that doesn't work for you, you'd be advised to know what the tradeoffs are with a regular tree. There are scenarios where B-trees are suboptimal.

Cache-obliviousness, which is still new, is also changing how we look at trees, since in one sense a B-tree is a hack on the basic tree structure to exploit locality. Representation matters more today as well. This is a longer conversation. Suffice to say I think this is an area of active and useful research, and wouldn't rule out either class of tree.

Re:Left-leaning red-black trees are hard to implement (2008) by nz on Monday December 01, 2014 @09:24AM (#8681059)
Well if you're storing integers or other other small (8-byte) elements, then sure. But if you are storing pointers to objects, then you'll have the overhead of a load (in the comparison function). If you are embedding the objects, then the larger it is the more "copy-overhead" you will have as you move these large elements around when re-balancing and so on. But I don't have the numbers for this, so it might be insignificant overhead. I have it on my todo-list to benchmark embedded-larger-elements and pointers to those elements. Anyway, just something to consider.