Re: Big files in ext2fs (but not i_osync)

Itai Nahshon (
Tue, 03 Mar 1998 09:01:41 +0200

MOLNAR Ingo wrote:
> doesnt this change the speed of bmap() from O(1) to O(log(N))? With the
> current scheme we exactly know where to look to get the index, with
> extents we have to binary-search every table?

This is still a winner if we actually use fewer indirect blocks
in the search.
My estimate is that a btree/extents based structure will pay for itself
only if the average extent for large files is more than 12 blocks.
I assume 3 words/extent on the leaf nodes. 2 words in internal nodes
and btree nodes 50% full on the average.
Small files can hold 5 extents right in the inode.

> And, why do we have to store
> both logical and physical blocks, is there any nontrivial translation
> between them?

The "logical" block is the file block number.
The "physical" block is the device block number.

Without both fields it is impossible to do a binary search
(just a linear search through the whole file) and also it is impossible
to have sparse files.


Itai Nahshon

- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to