lkml.org 
[lkml]   [1998]   [Mar]   [3]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: 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

\
 
 \ /
  Last update: 2005-03-22 13:41    [W:1.380 / U:0.016 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site