Messages in this thread | | | Date | Tue, 03 Mar 1998 09:01:41 +0200 | From | Itai Nahshon <> | Subject | Re: Big files in ext2fs (but not i_osync) |
| |
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 -- Itai Nahshon nahshon@actcom.co.il Also nahshon@vnet.ibm.com
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu
| |