lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  PHC 
Open Source and information security mailing list archives
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:	Wed, 13 May 2015 19:22:54 +0200
From:	"U.Mutlu" <>
Subject: Re: Htree concept

Eric Sandeen wrote on 05/13/2015 06:29 PM:
> On 5/13/15 10:37 AM, U.Mutlu wrote:
>> Hi,
>> I'm writing a toy-fs, and discover a major shortcoming
>> (finding a given child (dir/file) as fast as possible),
>> which other developers (ie. ext3/4) had encountered long ago too.
>> They introduced HTree. The info on HTree on the web is scarce
>> or I couldn't find the right texts/papers yet.
>> I wonder how HTree works on a conceptual basis.
>> Could a kind soul enligten me pls. TIA.
> Regarding htree details, did you look at:
> which points to:
> and more specifically,
> ?

Thanks, the wiki page and its refs I knew, but needed some more info.

Ok, it is written that HTree uses 32bit (or 64?) hashes for keys.
I wonder if it wouldn't be better if one instead would use that space
(32/64 bit) for storing the first n chars of the key (ie. of the dir/file name)
and keeping the directory entries in a sorted order on the disk,
and then do a bsearch instead of doing sequential table lookup using HTree?
I wonder what the "Tree"-part of HTree stand for in this context.
Am I right in my assumption that HTree mainly means the hashing mechanism,
but does not use any binary search mechanism for searching the key?


To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to
More majordomo info at

Powered by blists - more mailing lists