Suppose you have a Linux file system where the block size is 2K bytes, a disk address is 32 bits, and an i-node contains the disk addresses of the first 12 direct blocks of file, a single indirect block, and a double indirect block. Approximately, what is the largest file that can be represented by an i-node?
513 MBytes
Understanding Linux File System Structure and i-nodes
In a Linux file system, the i-node (index node) is a data structure that stores information about a file or directory, such as ownership, permissions, timestamps, and, crucially, the disk addresses of the blocks containing the file's actual data. The way these disk addresses are stored determines the maximum size a file can have.
The question describes a specific i-node structure with direct, single indirect, and double indirect blocks. Let's break down how each type of block contributes to the total file size.
Calculating File Size Contribution from Different Blocks
We are given the following information:
- Block size: 2 Kbytes
- Disk address size: 32 bits (which is 4 bytes, since 1 byte = 8 bits)
- i-node contains: 12 direct blocks, 1 single indirect block, 1 double indirect block
1. Direct Blocks
Direct blocks store the disk addresses of the file's data blocks directly within the i-node itself.
Number of direct blocks = 12
Size contributed by direct blocks = Number of direct blocks $\times$ Block size
Size contributed by direct blocks = $12 \times 2 \text{ Kbytes} = 24 \text{ Kbytes}$
2. Single Indirect Block
A single indirect block does not store file data directly. Instead, it stores the disk addresses of other data blocks. First, we need to figure out how many disk addresses can fit into one block.
Number of addresses per block = Block size / Disk address size
Block size = 2 Kbytes = $2 \times 1024 \text{ bytes} = 2048 \text{ bytes}$
Disk address size = 32 bits = 4 bytes
Number of addresses per block = $2048 \text{ bytes} / 4 \text{ bytes/address} = 512 \text{ addresses}$
A single indirect block contains 512 addresses, each pointing to a data block of size 2 Kbytes.
Size contributed by single indirect block = Number of addresses per block $\times$ Block size
Size contributed by single indirect block = $512 \times 2 \text{ Kbytes} = 1024 \text{ Kbytes}$
Since 1024 Kbytes = 1 Mbyte, the size contributed is 1 Mbyte.
3. Double Indirect Block
A double indirect block adds another level of indirection. It stores the disk addresses of *single indirect blocks*. Each of those single indirect blocks, in turn, stores addresses of data blocks.
A double indirect block contains 512 addresses (as calculated above). Each of these 512 addresses points to a single indirect block.
Each single indirect block can point to 512 data blocks.
Total data blocks pointed to by a double indirect block = (Number of addresses in double indirect block) $\times$ (Number of addresses in each single indirect block)
Total data blocks = $512 \times 512 = 262144$ blocks
Size contributed by double indirect block = Total data blocks $\times$ Block size
Size contributed by double indirect block = $262144 \times 2 \text{ Kbytes} = 524288 \text{ Kbytes}$
To convert Kbytes to Mbytes, we divide by 1024 (since 1 Mbyte = 1024 Kbytes).
Size contributed by double indirect block in Mbytes = $524288 \text{ Kbytes} / 1024 \text{ Kbytes/Mbyte} = 512 \text{ Mbytes}$
Calculating Total Maximum File Size
The total maximum file size is the sum of the sizes contributed by all types of blocks the i-node can reference.
Total size = Size (Direct Blocks) + Size (Single Indirect Block) + Size (Double Indirect Block)
Total size = 24 Kbytes + 1024 Kbytes + 524288 Kbytes
Total size = 1048 Kbytes + 524288 Kbytes
Total size = 525336 Kbytes
Now, let's convert the total size to Mbytes for easier comparison with the options.
Total size in Mbytes = $525336 \text{ Kbytes} / 1024 \text{ Kbytes/Mbyte}$
Total size in Mbytes $\approx 513 \text{ Mbytes}$
Therefore, the largest file size that can be represented by this i-node is approximately 513 Mbytes.
Summary of Calculations
| Block Type | Number of Blocks/Pointers | Size Contribution (Kbytes) | Size Contribution (Mbytes) |
|---|---|---|---|
| Direct Blocks | 12 | $12 \times 2 = 24$ | N/A |
| Single Indirect Block | 1 (points to 512 data blocks) | $512 \times 2 = 1024$ | 1 |
| Double Indirect Block | 1 (points to 512 single indirect blocks, which point to $512 \times 512$ data blocks) | $512 \times 512 \times 2 = 524288$ | 512 |
Total size = 24 Kbytes + 1 Mbyte + 512 Mbytes
Total size = 24 Kbytes + 513 Mbytes
Since 24 Kbytes is small compared to 513 Mbytes, the approximate largest file size is 513 Mbytes.
Revision Table: Linux File System i-node Structure
| Concept | Description |
|---|---|
| i-node | Stores file/directory metadata and block pointers. |
| Direct Blocks | Pointers within i-node directly to data blocks. |
| Single Indirect Block | A block containing pointers to data blocks. |
| Double Indirect Block | A block containing pointers to single indirect blocks. |
| Block Size | The size of a single data block on the disk. |
| Disk Address | A pointer indicating the location of a block on disk. |
Additional Information: Other Indirection Levels and File Systems
Some file systems also use triple indirect blocks for even larger files. A triple indirect block would point to double indirect blocks. The maximum file size is limited by the number of pointers in the i-node and the level of indirection supported. Different file systems (like ext2, ext3, ext4 in Linux) have variations in their i-node structure, block sizes, and address sizes, which affect the maximum file size they can support. The calculations performed here are specific to the parameters given in the problem.
Important Questions from Indexing - Teaching
Consider a B-tree of height h, minimum degree t ≥ 2 that contains any n-key, where n ≥ 1. Which of the following is correct?
In a B-Tree, each node represents a disk block. Suppose one block holds 8192 bytes. Each key uses 32 bytes. In a B-tree of order M there are M – 1 keys. Since each branch is on another disk block. We assume a branch is of 4 bytes. The total memory requirement for a non-leaf node is
The order of a leaf node in a B+ tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the value field is 9 bytes long and a block pointer is 6 bytes long, what is the order of the leaf node?
Suppose a B +tree is used for indexing a database file. Consider the following information :
size of the search key field = 10 bytes, block size = 1024 bytes, size of the record pointer = 9 bytes, size of the block pointer = 8 bytes.
Let K be the order of internal node and L be the order of leaf node of B +tree, then (K, L) = ______.
The clustering index is defined on the fields which are of type
