DragonFly kernel List (threaded) for 2008-06
Re: HAMMER Update 13-June-2008 - HEADS UP: MEDIA CHANGED AGAIN
:Maybe the question is why B+ trees are so popular in current file
:systems. I am certainly not expert enough to see all the implications
:of the selection of the tree structure on the implementation and
:performance of a file system, but what is the main reason why you
:chose B- trees?
B-Trees (generically, + or -) have very good lookup characteristics
for random-access devices. They first found wide-spread use in
relational databases something like 20 years ago.
Basically the idea is to use a B-Tree with a very large radix. In
the case of HAMMER, I am using a radix of 64 and could go all the
way to 256 (the maximum that would fit in a 16K HAMMER buffer) if
I wanted to. Use of a large radix greatly reduces the number of
discrete I/O's (and related seeks) needed to locate an object or
For example, a lookup of a filename in a directory containing
one hundred million files would only require 6 discrete I/O's.
The caching characteristics of B-Trees are also really, really good.
Not only can one cache pointers into the B-Tree and avoid starting
searches from the root of the tree, but the higher layers of the B-Tree
tend to be very well represented in system (memory) caches and,
in particular, the node paths going the root to the 'vicinity' of
the object or record you want to locate are very easy to cache.