On Mon, Nov 14, 2011 at 8:33 AM, Edward Ned Harvey
<opensolarisisdeadlongliveopensola...@nedharvey.com> wrote:
>> From: zfs-discuss-boun...@opensolaris.org [mailto:zfs-discuss-
>> boun...@opensolaris.org] On Behalf Of Paul Kraus
>> Is it really B-Tree based? Apple's HFS+ is B-Tree based and falls
>> apart (in terms of performance) when you get too many objects in one
>> FS, which is specifically what drove us to ZFS. We had 4.5 TB of data
> According to wikipedia, btrfs is a b-tree.
> I know in ZFS, the DDT is an AVL tree, but what about the rest of the
> filesystem?

ZFS directories are hashed.  Aside from this, the filesystem (and
volume) have a tree structure, but that's not what's interesting here
-- what's interesting is how directories are indexed.

> 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.

Also, b-trees are O(log_b N), where b is the number of entries
per-node.  6e7 entries/directory probably works out to 2-5 reads
(assuming 0% cache hit rate) depending on the size of each directory
entry and the size of the b-tree blocks.

zfs-discuss mailing list

Reply via email to