Re: Ext2fs and hashed table.

Matthias Urlichs (smurf@work.smurf.noris.de)
2 Jun 1997 22:36:55 +0200


R.E.Wolff@BitWizard.nl (Rogier Wolff) writes:
>
> You know, apple's fast filesystem (HFS, whatever that stands for)
> uses btrees. But it has a unified name space. Thus
>
"Unified name space" isn't quite right. It's just that all the directory
entries are stored in one big file, with one inode, instead of one file per
directory.

Much more interesting, is the fact that the file's position on disk are
stored as <block number,length> tuples (the first three are stored in the
"inode", the rest in another big b-tree), not as a direct/indirect/whatever
list of blocks. I'd like to see that (minus the b-tree) as an ext2fs
extension, just to see whether it speeds things up any. It should,
especially for big files (it's much better to have "this file starts at
block #314159 and continues for 1234567 blocks" than to read a triple-
-double-single-indirect block every time somebody wants to read the last a
character from a big file). Holes can be represented by block number zero.

> find / -name blabla\*
>
> is an operation that you can do REALLY FAST on an HFS filesystem.
>
Well, you still have to scan through the entire B-tree because the index is
<directoryID,filename>. The speedup comes more from being able to do all
this with one system call (not "one call per directory", but "one call per
file you end up finding"), which lets the OS and the disk do some readahead.

-- 
In English, every word can be verbed.
Would that it were so in our programming languages.
-- 
Matthias Urlichs         \  noris network GmbH  /  Xlink-POP Nürnberg 
Schleiermacherstraße 12   \   Linux+Internet   /   EMail: urlichs@noris.de
90491 Nürnberg (Germany)   \    Consulting+Programming+Networking+etc'ing
   PGP: 1024/4F578875   1B 89 E2 1C 43 EA 80 44  15 D2 29 CF C6 C7 E0 DE
       Click <A HREF="http://info.noris.de/~smurf/finger">here</A>.    42