News for hackers. Stuff that matters.
Re:Coding tricks I learnt at Apple by endtime on Friday June 10, 2011 @01:11PM (#2641600)
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?
Re:Coding tricks I learnt at Apple by tptacek on Friday June 10, 2011 @01:30PM (#2641675)
I'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.
Re:Coding tricks I learnt at Apple by ckuehne on Saturday June 11, 2011 @07:03AM (#2643636)
So 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/.

Re:Coding tricks I learnt at Apple by tptacek on Saturday June 11, 2011 @03:51PM (#2644682)
You know that's not what I'm saying. You're just trying to assert nerd dominance.
Re:Coding tricks I learnt at Apple by endtime on Friday June 10, 2011 @02:50PM (#2641996)
Ah, 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.
Re:Coding tricks I learnt at Apple by eck on Friday June 10, 2011 @01:42PM (#2641717)
It'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.
Re:Coding tricks I learnt at Apple by wickedchicken on Friday June 10, 2011 @01:42PM (#2641716)
Well, 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.
Re:Coding tricks I learnt at Apple by jamn on Saturday June 11, 2011 @04:29AM (#2643475)
B-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)

Re:Coding tricks I learnt at Apple by btilly on Friday June 10, 2011 @05:15PM (#2642443)
It 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-obli... for one strategy to do that. (With that structure lookups become faster, but walking the tree in order becomes difficult.)
Re:Coding tricks I learnt at Apple by wickedchicken on Saturday June 11, 2011 @08:29PM (#2645268)
This 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!
Re:Coding tricks I learnt at Apple by JoeMoreno on Friday June 10, 2011 @06:47PM (#2642697)
Sorry about my typo. I really meant binary trees, not b-trees.