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:
http://en.wikipedia.org/wiki/HTree
which points to:
http://ext2.sourceforge.net/2005-ols/paper-html/node3.html
and more specifically,
http://web.archive.org/web/20131203105316/http://www.linuxshowcase.org/2001/full_papers/phillips/phillips_html/index.html
?
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?
--
Thx
Uenal
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
