4 ms·

If you're interested in this stuff, you might want to check out the draft paper linked below. It benchmarks performance and memory efficiency of various logarit

by nz 12y ago

If you're interested in this stuff, you might want to check out the draft paper linked below. It benchmarks performance and memory efficiency of various logarithmic time sorting data structures. It's a work in progress, and feedback is always welcome :) http://nickziv.files.wordpress.com/2014/02/vis_ds.pdf http://nickziv.files.wordpress.com/2014/02/vis_ds.pdf

adrianN 12y ago
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.
- nz 12y ago
  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.
- kcl 12y ago
  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.

by nz 12y ago

adrianN 12y ago

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.

nz 12y ago
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.
kcl 12y ago
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.