Re: Htree concept

[Theodore Ts'o <tytso@mit.edu>]

On Wed, May 13, 2015 at 07:37:36PM +0200, U.Mutlu wrote:
> I think I slowly grasp how HTree works: it keeps a (rb/avl tree)
> b*tree-db (I guess it stores it on disk) of the hashes (as keys).

The reason for using hashes is it keeps the fanout of the tree very
high, which in turn keeps the depth of the tree very short.  This
means that we can do search a very large directory using at most three
disk reads (two levels of internal node, where each node can store up
to 340 hashes plus pointers the next level of the tree, plus a
directory leaf block).

> In contrast to that here my idea: keep the hdr blocks (ie. where the
> dir/file names are) always in a sorted order. Then a bsearch should be doable.
> This would eliminate the need for any b*tree-db usage.

The problem with using a binary search is (a) it's more expensive to
search each disk read divides the search space in half (in contrast,
in the best case using htree, the first disk read can divide the
search space by factor of 340), and (b) insertions are very expensive;
suppose you have a 400 megabyte directory, and you need to insert a
filename into the very beginning of the list.  You will have to
performance 800 megabytes of I/O to make room for directory entry, if
you want to keep all of the directory entries sorted.

Cheers,

					- Ted