5 ms·
I agree that the article was wrong, but...is there really never a case in which a B-tree is a useful in-memory index, rather than a storage technique?
by endtime 15y ago
I agree that the article was wrong, but...is there really never a case in which a B-tree is a useful in-memory index, rather than a storage technique?
- tptacek 15y agoI'm only commenting because of the "job interview" comment, but when someone compares hash tables to B-trees, I usually assume (fairly or not) that they don't really know what a B-tree is.
- endtime 15y agoAh, thanks for clarifying. I had to implement a B+-tree using only a 2D byte array as a sophomore, so I don't think I'll ever be able to forget how they work.
- ckuehne 15y agoSo what you are saying is that the whole database research community does not really know what a B-Tree is [1]? [1] Every database implementation techniques lecture compares the two. See, e.g., http://infolab.stanford.edu/~hyunjung/cs346/ http://infolab.stanford.edu/~hyunjung/cs346/.
- tptacek 15y agoYou know that's not what I'm saying. You're just trying to assert nerd dominance.
- wickedchicken 15y agoWell, you can walk spatial partitions with trees in ways that become clunky with hashes (taking a branch means all children are 'near' each other). Also, B-trees might work better in cached architectures -- this is certainly true with respect to disk accesses but I'm not sure if that carries over to L3/L2/L1 cache.
- btilly 15y agoIt does carry over to L3/L2/L1 cache, but only if the tree is designed to benefit from that. See http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-obli... for one strategy to do that. (With that structure lookups become faster, but walking the tree in order becomes difficult.)
- wickedchicken 15y agoThis is a really great article and I wish I could give you some more points to make this appear higher. I once used a cache-oblivious matrix transpose algorithm that was startlingly simple and effective but I didn't know the approach had been so widely applied. Thanks!
- jamn 15y agoB-Trees actually have superior cache performance compared to other types of trees (such as T-Trees or BST Trees). In part, this is because B-Trees have a higher density of actual data to pointers. There is a tradeoff of computation (doing binary search inside the node) and amount of storage (keeping less pointers). In environments where memory access is much more expensive than a CPU instruction, it is preferable to perform these computations than to have to read all the extra pointer data to jump to the right places. In fact, a breed of cache-friendly data structures are precisely based on the B+Trees but with even less pointers, having the algorithm compute these pointers instead (CSS-, CSB-Trees)
- eck 15y agoIt's possible. There are parallels between main memory and disks. A disk seek gets you hundreds or thousands of bytes and requires (blocking for) millions of cpu cycles; a cache line fill gets you 64 (sometimes) bytes and requires (spinning for) hundreds of cpu cycles. You want to minimize both of those, but with memory, the difference is much less dramatic.
- JoeMoreno 15y agoSorry about my typo. I really meant binary trees, not b-trees.