> From: Nico Williams [mailto:n...@cryptonector.com] > > > B-trees should be logarithmic time, which is the best O() you can possibly > > achieve. So if HFS+ is dog slow, it's an implementation detail and not a > > general fault of b-trees. > > Hash tables can do much better than O(log N) for searching: O(1) for > best case, and O(n) for the worst case.
You're right to challenge me saying O(log) is the best you can possibly achieve - The assumption I was making is that the worst case is what matters, and that's not always true. Which is better? An algorithm whose best case and worse case are both O(log n), or an algorithm that takes O(1) in the best case and O(n) in the worst case? The answer is subjective - and the question might be completely irrelevant, as it doesn't necessarily relate to any of the filesystems we're talking about anyway. ;-) _______________________________________________ zfs-discuss mailing list zfs-discuss@opensolaris.org http://mail.opensolaris.org/mailman/listinfo/zfs-discuss
