On Mon, Nov 14, 2011 at 8:33 AM, Edward Ned Harvey
>> 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
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