Messages in this thread | | | From | (Matthias Urlichs) | Subject | Re: Ext2fs and hashed table. | Date | 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
| |