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. Nico -- _______________________________________________ zfs-discuss mailing list zfs-discuss@opensolaris.org http://mail.opensolaris.org/mailman/listinfo/zfs-discuss
