[prev in list] [next in list] [prev in thread] [next in thread] 

List:       zfs-discuss
Subject:    Re: [zfs-discuss] about btrfs and zfs
From:       Edward Ned Harvey <opensolarisisdeadlongliveopensolaris () nedharvey ! com>
Date:       2011-11-15 0:21:40
Message-ID: 000001cca32c$8f4eb3d0$adec1b70$ () nedharvey ! com
[Download RAW message or body]

> From: Nico Williams [mailto:nico@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


[prev in list] [next in list] [prev in thread] [next in thread]