Re: Ext2fs and hashed table.
Jan Kasprzak (kas@informatics.muni.cz)
Wed, 04 Jun 1997 12:07:04 +0200
Stephen C. Tweedie pise:
: smurf@work.smurf.noris.de (Matthias Urlichs) writes:
: > 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 already on the ext2fs TODO list. :) Yes, it will speed things
: up, mainly by reducing the size of the indirect mapping data structure
: and hence the number of IOs required to map a block.
:
: The main problem with this technique is that it completely falls apart
: when you consider Unix semantics for files with holes --- you end up
: having to reshuffle the entire extent map any time you insert new data
: by writing into a hole. The current plan is simply to convert
: on-the-fly from extent mapped to direct indexed block mapping if such
: a write occurs.
I think there will be a performance penalty for random access
to the file -- in the standard scheme after lseek() you exactly know
the block pointing to the data (or the index of the appropriate indirect
block). Thus you can access any byte in the file after at most
4 disk operations (inode and three levels of indirect blocks).
In the new scheme you will have to walk through the direct entries
and probably through the part of b-tree (which can be
O(log (index_in_the_file)) operation).
Am I wrong?
-Yenya
--
\ Jan "Yenya" Kasprzak <kas at fi.muni.cz> http://www.fi.muni.cz/~kas/
\\ PGP: finger kas at aisa.fi.muni.cz 0D99A7FB206605D7 8B35FCDE05B18A5E //
\\\ Czech Linux Homepage: http://www.fi.muni.cz/~kas/linux/ ///
/// die_if_kernel("Penguin instruction from Penguin mode??!?!", regs); \\\
// -- from linux/arch/sparc64/kernel/traps.c \\