Indexed Allocation - Learning Module

Loading content...

0/227

Multi-Level Index

Scaling Beyond Limits

A file system designer faces a fundamental constraint: the inode has fixed size. Whether you allocate 128 bytes, 256 bytes, or 512 bytes for each inode, you can only fit a limited number of direct pointers. With 12 direct pointers and 4KB blocks, you can address only 48KB directly.

But files can be massive—terabytes for databases, petabytes for scientific datasets. How do we bridge the gap between a fixed-size inode and arbitrarily large files?

The answer is multi-level indexing—a hierarchical tree of pointers that grows as needed, using the same block size for index blocks as for data blocks. This elegant solution provides bounded access time while supporting files of virtually unlimited size.

What You Will Learn

By the end of this page, you will understand the structure and purpose of single, double, and triple indirect blocks, calculate maximum file sizes for any block/pointer configuration, trace through complete block lookup examples with multi-level indirection, and appreciate why the Unix inode design has remained essentially unchanged for 50 years.

The Indirection Hierarchy

Multi-level indexing introduces layers of indirection between the inode and data blocks. Each level adds a factor of expansion equal to the number of pointers that fit in one block.

The Four Levels:

Direct and Indirect Pointer Types

•Direct Pointers — Point directly to data blocks. No indirection. Fastest access path. Typically 12 in the inode.
•Single Indirect Pointer — Points to a block containing data block pointers. One level of indirection. Adds pointers_per_block more blocks.
•Double Indirect Pointer — Points to a block of single indirect pointers. Two levels. Adds pointers_per_block² more blocks.
•Triple Indirect Pointer — Points to a block of double indirect pointers. Three levels. Adds pointers_per_block³ more blocks.

Converting Mermaid diagram...

Single Indirect Block

The single indirect block is the first expansion point. It's simply a block filled with data block pointers, with no embedded metadata—just a flat array of addresses.

Structure:

With a 4KB block and 8-byte pointers:

One indirect block holds 4096 ÷ 8 = 512 pointers
Each pointer addresses one 4KB data block
Total capacity: 512 × 4KB = 2MB

When It's Used:

Logical blocks 12–523 (in the classic 12-direct-pointer scheme) are addressed via the single indirect block.

single_indirect.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
 * Single Indirect Block Access
 * 
 * Reading a block in the single indirect range requires:
 * 1. Reading the indirect block (unless cached)
 * 2. Extracting the data block pointer
 * 3. Reading the data block
 *
 * Total: 2 disk reads (or 1 if indirect block is cached)
 */
 
#define BLOCK_SIZE          4096
#define POINTER_SIZE        8
#define PTRS_PER_BLOCK      (BLOCK_SIZE / POINTER_SIZE)  /* 512 */
#define DIRECT_BLOCKS       12
 
struct inode {
    /* ... metadata ... */
    block_ptr_t     direct[DIRECT_BLOCKS];
    block_ptr_t     indirect;           /* Single indirect */
    block_ptr_t     double_indirect;
    block_ptr_t     triple_indirect;
};
 
/*
 * Look up a block in the single indirect range
 * 
 * Logical blocks 12 through 523 are addressed here.
 */
block_ptr_t lookup_single_indirect(struct inode *inode, 
                                   uint64_t logical_block) {
    /* Verify this block is in single indirect range */
    if (logical_block < DIRECT_BLOCKS || 
        logical_block >= DIRECT_BLOCKS + PTRS_PER_BLOCK) {
        return 0;  /* Not in single indirect range */
    }
    
    /* Calculate index within the indirect block */
    uint64_t indirect_index = logical_block - DIRECT_BLOCKS;
    
    /* Read the indirect block (may be cached) */
    if (inode->indirect == 0) {
        return 0;  /* Sparse file hole */
    }
    
    block_ptr_t *indirect_block = read_block_cached(inode->indirect);
    
    /* Extract and return the data block address */
    return indirect_block[indirect_index];
}
 
/*
 * Example: Reading logical block 200
 * 
 * Given: logical_block = 200
 * 
 * Step 1: Is it in direct range? (0-11)
 *   200 >= 12, so no
 * 
 * Step 2: Is it in single indirect range? (12-523)
 *   200 < 524, so yes!
 * 
 * Step 3: Calculate index in indirect block
 *   indirect_index = 200 - 12 = 188
 * 
 * Step 4: Read inode->indirect block (say, block 5000)
 *   indirect_block[188] = 7842
 * 
 * Step 5: Return 7842 as the physical block
 * 
 * Data disk offset: 7842 × 4096 = 32,116,736 bytes
 */

Double Indirect Block

The double indirect block introduces a second level of indirection, squaring the addressing capacity. The inode's double indirect pointer points to a block of pointers, each of which points to another block of pointers, which finally point to data blocks.

Structure:

Level 1: 1 block containing 512 pointers to level-2 blocks
Level 2: Up to 512 blocks, each containing 512 data block pointers
Total pointers: 512 × 512 = 262,144
Total capacity: 262,144 × 4KB = 1 GB

Double Indirect Block Mechanics
Level	Block Count	Pointer Type	Points To
Inode	N/A	double_indirect ptr	Level 1 block
Level 1	1 block	512 pointers	Level 2 blocks
Level 2	Up to 512 blocks	262,144 total pointers	Data blocks
Data	Up to 262,144 blocks	N/A	Actual file data

double_indirect.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
 * Double Indirect Block Access
 * 
 * Requires traversing two levels of indirect blocks:
 * inode → level1 block → level2 block → data block
 * 
 * Total: 3 disk reads (or fewer if blocks are cached)
 */
 
/*
 * Look up a block in the double indirect range
 * 
 * Logical blocks 524 through 262,667 are addressed here.
 */
block_ptr_t lookup_double_indirect(struct inode *inode,
                                   uint64_t logical_block) {
    /* Calculate range boundaries */
    const uint64_t single_end = DIRECT_BLOCKS + PTRS_PER_BLOCK;  /* 524 */
    const uint64_t double_end = single_end + 
                                PTRS_PER_BLOCK * PTRS_PER_BLOCK;  /* 262,668 */
    
    /* Verify this block is in double indirect range */
    if (logical_block < single_end || logical_block >= double_end) {
        return 0;  /* Not in double indirect range */
    }
    
    /* Offset within double indirect address space */
    uint64_t offset = logical_block - single_end;
    
    /* Calculate indices at each level */
    uint64_t level1_index = offset / PTRS_PER_BLOCK;  /* Which L2 block? */
    uint64_t level2_index = offset % PTRS_PER_BLOCK;  /* Which entry in L2? */
    
    /* Read level 1 (double indirect block) */
    if (inode->double_indirect == 0) {
        return 0;  /* Sparse hole */
    }
    
    block_ptr_t *level1 = read_block_cached(inode->double_indirect);
    
    /* Read level 2 block */
    if (level1[level1_index] == 0) {
        return 0;  /* Sparse hole */
    }
    
    block_ptr_t *level2 = read_block_cached(level1[level1_index]);
    
    /* Return the data block address */
    return level2[level2_index];
}
 
/*
 * Example: Reading logical block 10,000
 * 
 * Given: logical_block = 10,000
 * 
 * Step 1: Verify range
 *   10,000 >= 524 (beyond single indirect)
 *   10,000 < 262,668 (within double indirect)
 *   → Double indirect applies
 * 
 * Step 2: Calculate offset
 *   offset = 10,000 - 524 = 9,476
 * 
 * Step 3: Calculate level 1 index
 *   level1_index = 9,476 / 512 = 18
 *   (We need the 19th L2 block, index 18)
 * 
 * Step 4: Calculate level 2 index
 *   level2_index = 9,476 % 512 = 260
 *   (We need entry 260 within that L2 block)
 * 
 * Step 5: Read inode->double_indirect (say, block 6000)
 *   level1[18] = block 7542
 * 
 * Step 6: Read block 7542
 *   level2[260] = block 15847
 * 
 * Step 7: Return 15847 as the physical data block
 * 
 * Total disk reads: 2 (L1 and L2) + 1 (data) = 3
 */

Triple Indirect Block

The triple indirect block adds a third level of indirection, cubing the addressing capacity. This is typically the maximum level of indirection in production file systems.

Structure:

Level 1: 1 block → 512 pointers to level-2 blocks
Level 2: 512 blocks → 262,144 pointers to level-3 blocks
Level 3: 262,144 blocks → 134,217,728 data block pointers
Total capacity: 134,217,728 × 4KB = 512 GB

Combined with all levels, maximum file size ≈ 514 GB (though ext4 uses 48-bit block addressing to support up to 16TB)

triple_indirect.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
 * Triple Indirect Block Access
 * 
 * The deepest level of indirection, requiring 3 indirect block reads.
 * Maximum data blocks addressable: 512³ = 134,217,728
 */
 
block_ptr_t lookup_triple_indirect(struct inode *inode,
                                   uint64_t logical_block) {
    /* Calculate boundaries */
    const uint64_t single_end = DIRECT_BLOCKS + PTRS_PER_BLOCK;
    const uint64_t double_end = single_end + 
                                (uint64_t)PTRS_PER_BLOCK * PTRS_PER_BLOCK;
    const uint64_t triple_end = double_end +
                                (uint64_t)PTRS_PER_BLOCK * PTRS_PER_BLOCK * 
                                PTRS_PER_BLOCK;
    
    /* Verify range */
    if (logical_block < double_end || logical_block >= triple_end) {
        return 0;  /* Not in triple indirect range */
    }
    
    /* Offset within triple indirect address space */
    uint64_t offset = logical_block - double_end;
    
    /* Calculate indices at each of the three levels */
    uint64_t pps = PTRS_PER_BLOCK * PTRS_PER_BLOCK;  /* 262,144 */
    
    uint64_t level1_index = offset / pps;
    uint64_t remaining = offset % pps;
    uint64_t level2_index = remaining / PTRS_PER_BLOCK;
    uint64_t level3_index = remaining % PTRS_PER_BLOCK;
    
    /* Traverse three levels */
    if (inode->triple_indirect == 0) return 0;
    
    block_ptr_t *L1 = read_block_cached(inode->triple_indirect);
    if (L1[level1_index] == 0) return 0;
    
    block_ptr_t *L2 = read_block_cached(L1[level1_index]);
    if (L2[level2_index] == 0) return 0;
    
    block_ptr_t *L3 = read_block_cached(L2[level2_index]);
    
    return L3[level3_index];
}
 
/*
 * Complete file offset to physical block translation
 */
block_ptr_t logical_to_physical(struct inode *inode, 
                                uint64_t logical_block) {
    /* Direct blocks: 0-11 */
    if (logical_block < DIRECT_BLOCKS) {
        return inode->direct[logical_block];
    }
    
    /* Single indirect: 12-523 */
    uint64_t remaining = logical_block - DIRECT_BLOCKS;
    if (remaining < PTRS_PER_BLOCK) {
        return lookup_single_indirect(inode, logical_block);
    }
    
    /* Double indirect: 524-262,667 */
    remaining -= PTRS_PER_BLOCK;
    if (remaining < (uint64_t)PTRS_PER_BLOCK * PTRS_PER_BLOCK) {
        return lookup_double_indirect(inode, logical_block);
    }
    
    /* Triple indirect: 262,668+ */
    return lookup_triple_indirect(inode, logical_block);
}

Why Stop at Triple?

Triple indirection provides ~512GB capacity with 4KB blocks and 8-byte pointers. Quadruple indirection would provide ~256TB, but adds latency. Modern file systems prefer extent-based or 48/64-bit addressing over deeper indirection trees.

Maximum File Size Calculations

A critical skill for file system understanding is calculating maximum file sizes for different configurations. The formula combines all levels of the indirection hierarchy.

Maximum File Size Formula

Max Size = (D + P + P² + P³) × B

Where:

D = Number of direct pointers (typically 12)
P = Pointers per block = B / sizeof(pointer)
B = Block size in bytes

Maximum File Sizes by Configuration
Block Size	Pointer Size	Pointers/Block	Max File Size	Notes
1 KB	4 bytes	256	~16 GB	Early Unix systems
4 KB	4 bytes	1024	~4 TB	32-bit systems
4 KB	8 bytes	512	~514 GB	64-bit pointers
8 KB	8 bytes	1024	~8 TB	Larger blocks
64 KB	8 bytes	8192	~32 PB	Very large blocks

max_size_calculator.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*
 * Maximum File Size Calculator
 * 
 * Computes the theoretical maximum file size for any
 * block size and pointer size configuration.
 */
 
#include <stdio.h>
#include <stdint.h>
 
typedef struct {
    uint64_t direct_bytes;
    uint64_t single_indirect_bytes;
    uint64_t double_indirect_bytes;
    uint64_t triple_indirect_bytes;
    uint64_t total_max_bytes;
    uint64_t total_max_blocks;
} file_size_limits_t;
 
file_size_limits_t calculate_max_file_size(
    uint64_t block_size,      /* In bytes */
    uint64_t pointer_size,    /* In bytes */
    uint64_t direct_count     /* Number of direct pointers */
) {
    file_size_limits_t limits;
    
    uint64_t ptrs_per_block = block_size / pointer_size;
    
    /* Direct blocks */
    limits.direct_bytes = direct_count * block_size;
    
    /* Single indirect: one block of pointers */
    limits.single_indirect_bytes = ptrs_per_block * block_size;
    
    /* Double indirect: P blocks each with P pointers */
    limits.double_indirect_bytes = 
        ptrs_per_block * ptrs_per_block * block_size;
    
    /* Triple indirect: P² blocks each with P pointers */
    limits.triple_indirect_bytes = 
        ptrs_per_block * ptrs_per_block * ptrs_per_block * block_size;
    
    limits.total_max_bytes = 
        limits.direct_bytes +
        limits.single_indirect_bytes +
        limits.double_indirect_bytes +
        limits.triple_indirect_bytes;
    
    limits.total_max_blocks = limits.total_max_bytes / block_size;
    
    return limits;
}
 
void print_limits(const char *name, uint64_t block_size, 
                  uint64_t pointer_size) {
    file_size_limits_t l = calculate_max_file_size(
        block_size, pointer_size, 12
    );
    
    printf("\n=== %s ===\n", name);
    printf("Block size: %lu bytes, Pointer size: %lu bytes\n",
           block_size, pointer_size);
    printf("Pointers per block: %lu\n", block_size / pointer_size);
    printf("\nAddressable by level:\n");
    printf("  Direct:          %12lu bytes (%lu KB)\n", 
           l.direct_bytes, l.direct_bytes / 1024);
    printf("  Single indirect: %12lu bytes (%lu MB)\n",
           l.single_indirect_bytes, l.single_indirect_bytes / (1024*1024));
    printf("  Double indirect: %12lu bytes (%lu GB)\n",
           l.double_indirect_bytes, 
           l.double_indirect_bytes / (1024*1024*1024));
    printf("  Triple indirect: %12lu bytes (%lu GB)\n",
           l.triple_indirect_bytes,
           l.triple_indirect_bytes / (1024*1024*1024));
    printf("\nMAXIMUM FILE SIZE: %lu bytes\n", l.total_max_bytes);
}
 
int main() {
    /* Standard ext4 configuration */
    print_limits("ext4 (4KB blocks, 8-byte pointers)", 4096, 8);
    
    /* Larger blocks */
    print_limits("Large block FS (64KB blocks, 8-byte pointers)", 65536, 8);
    
    /* Legacy 32-bit system */
    print_limits("32-bit system (4KB blocks, 4-byte pointers)", 4096, 4);
    
    return 0;
}
 
/*
 * Expected output for ext4 (4KB, 8-byte):
 * 
 * Pointers per block: 512
 * Direct:          48 KB
 * Single indirect: 2 MB  
 * Double indirect: 1 GB
 * Triple indirect: 512 GB
 * MAXIMUM FILE SIZE: ~514 GB
 */

Complete Block Lookup Example

Let's trace through a complete example: reading byte 100,000,000 from a file. We'll show every step of the multi-level lookup process.

complete_lookup_trace.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/*
 * Complete Block Lookup Trace
 * 
 * Goal: Read 1 byte at file offset 100,000,000
 * Configuration: 4KB blocks, 8-byte pointers, 12 direct blocks
 */
 
/* Constants */
#define BLOCK_SIZE      4096
#define PTRS_PER_BLOCK  512  /* 4096 / 8 */
#define DIRECT_COUNT    12
 
/*
 * Trace: Where is byte 100,000,000?
 */
void trace_lookup_100M() {
    uint64_t byte_offset = 100000000;  /* 100 million bytes */
    
    /*
     * Step 1: Calculate logical block number
     * 
     * logical_block = 100,000,000 / 4096 = 24,414
     * offset_in_block = 100,000,000 % 4096 = 1,504
     */
    uint64_t logical_block = byte_offset / BLOCK_SIZE;  /* 24,414 */
    uint64_t offset_in_block = byte_offset % BLOCK_SIZE; /* 1,504 */
    
    printf("Byte offset: %lu\n", byte_offset);
    printf("Logical block: %lu, offset in block: %lu\n\n",
           logical_block, offset_in_block);
    
    /*
     * Step 2: Determine which pointer level addresses this block
     * 
     * Direct range:          0 - 11        (12 blocks)
     * Single indirect range: 12 - 523      (512 blocks)  
     * Double indirect range: 524 - 262,667 (262,144 blocks)
     * Triple indirect range: 262,668+
     * 
     * Block 24,414 is in the DOUBLE INDIRECT range!
     */
    
    uint64_t direct_end = DIRECT_COUNT;                    /* 12 */
    uint64_t single_end = direct_end + PTRS_PER_BLOCK;     /* 524 */
    uint64_t double_end = single_end + 
                          (uint64_t)PTRS_PER_BLOCK * PTRS_PER_BLOCK; /* 262,668 */
    
    printf("24,414 >= 12 (beyond direct)\n");
    printf("24,414 >= 524 (beyond single indirect)\n");
    printf("24,414 < 262,668 (within double indirect!)\n\n");
    
    /*
     * Step 3: Calculate indices within double indirect structure
     * 
     * Offset from start of double indirect range:
     *   24,414 - 524 = 23,890
     * 
     * Level 1 index (which L2 block?):
     *   23,890 / 512 = 46
     * 
     * Level 2 index (which entry in L2?):
     *   23,890 % 512 = 338
     */
    uint64_t di_offset = logical_block - single_end;  /* 23,890 */
    uint64_t L1_index = di_offset / PTRS_PER_BLOCK;   /* 46 */
    uint64_t L2_index = di_offset % PTRS_PER_BLOCK;   /* 338 */
    
    printf("Double indirect offset: %lu\n", di_offset);
    printf("Level 1 index: %lu (47th L2 block)\n", L1_index);
    printf("Level 2 index: %lu (339th entry in that L2 block)\n\n", L2_index);
    
    /*
     * Step 4: Follow the pointers (assuming these block addresses)
     * 
     * inode.double_indirect = 8000  (L1 block address)
     * 
     * Read block 8000, entry [46] = 8500  (L2 block address)
     * 
     * Read block 8500, entry [338] = 75432  (DATA block address)
     */
    printf("Disk reads:\n");
    printf("  1. Read inode.double_indirect → block 8000\n");
    printf("  2. Read block 8000[46] → block 8500\n");
    printf("  3. Read block 8500[338] → data block 75432\n\n");
    
    /*
     * Step 5: Calculate final disk offset for the data
     * 
     * Data block 75432 starts at byte 75432 × 4096 = 308,969,472
     * Our byte is at offset 1,504 within that block
     * Final disk position: 308,969,472 + 1,504 = 308,970,976
     */
    uint64_t data_block = 75432;
    uint64_t disk_byte = (data_block * BLOCK_SIZE) + offset_in_block;
    
    printf("Final answer:\n");
    printf("  Physical block: %lu\n", data_block);
    printf("  Disk byte offset: %lu\n", disk_byte);
    printf("  Disk read: pread(fd, buf, 1, %lu)\n", disk_byte);
    
    /*
     * Summary:
     * - 2 disk reads for navigation (L1, L2)
     * - 1 disk read for data
     * - Total: 3 disk reads
     * 
     * This is O(1) - same cost whether byte 100M or byte 100B!
     */
}

Performance Analysis

Multi-level indexing introduces a performance tradeoff: larger files require more disk reads for random access. However, caching dramatically improves real-world performance.

Access Latency by File Region and Cache State
File Region	Cold Cache (HDD)	Warm Cache	Hot Cache (all cached)
Direct (0-48KB)	10ms (1 read)	0.01ms	0ms
Single Indirect (48KB-2MB)	20ms (2 reads)	10ms (1 read)	0ms
Double Indirect (2MB-1GB)	30ms (3 reads)	10-20ms	0ms
Triple Indirect (1GB+)	40ms (4 reads)	10-30ms	0ms

Performance Optimization Strategies

•Aggressive Inode Caching — Keep inodes of open files in memory permanently
•Indirect Block Caching — Cache indirect blocks with high priority since many data blocks share them
•Read-Ahead — When reading sequentially, prefetch upcoming indirect blocks
•Hot Path Optimization — Most file I/O hits direct pointers; optimize that path heavily
•SSD Advantage — Random reads are ~100× faster on SSDs, making multi-level lookup nearly imperceptible

The 80/20 Rule

Studies show 80%+ of file accesses hit the direct pointer range (files under 48KB). The majority of remaining accesses hit single indirect. Double and triple indirect are used only for the largest files, which are often accessed sequentially anyway.

Real-World Implementations

Different file systems implement multi-level indexing with variations on the classic Unix scheme. Here's how major file systems approach the problem:

ext4 supports both traditional indirect pointers and extent trees:

Extents Mode (default): Uses a B-tree of extents for efficient contiguous region mapping
Indirect Mode (legacy): Traditional 12 direct + 3 indirect pointer scheme
48-bit block addressing: Supports files up to 16TB with 4KB blocks
Automatic migration: Can convert between modes as needed

ext4_addressing.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* ext4 inode block addressing */
struct ext4_inode {
    /* ... metadata (100 bytes) ... */
    
    /* 60 bytes for block mapping */
    union {
        /* Traditional indirect pointers */
        struct {
            __le32 i_block[15];  /* 12 direct + 3 indirect */
        };
        
        /* Or extent tree (more common) */
        struct ext4_extent_header i_extent_header;
        /* Followed by 4 extents or index nodes */
    };
};
 
/* With extents, a 1GB contiguous file needs just 1 extent!
 * Traditional pointers would need 262,144+ entries. */

Summary: The Elegant Hierarchy

Multi-level indexing is a masterpiece of computer science design. It solves an inherently difficult problem—mapping arbitrarily large files with a fixed-size inode—through a simple recursive structure that grows only as needed.

Key Takeaways

•Fixed inode, unlimited files — A 256-byte inode can address 500GB+ files through hierarchical pointers.
•Bounded access time — Maximum 4 disk reads regardless of file size or access position.
•O(P^n) capacity growth — Each level multiplies capacity by pointers-per-block.
•Caching is essential — Indirect blocks are reused across many data accesses.
•Direct is most common — Optimize the direct pointer path since most files are small.
•Extents are the future — Modern systems use extent-based addressing for better space efficiency.

Module Complete!

You've now mastered indexed allocation—from the fundamental concept of index blocks through direct pointers, random access support, overhead analysis, and multi-level indexing. This knowledge is essential for understanding how every modern file system, from ext4 and XFS to NTFS and APFS, manages file data on disk.

Module Complete

Congratulations! You now possess a deep understanding of indexed allocation—the foundation of modern file system design. You can calculate file size limits, trace block lookups through multi-level indirection, and evaluate the tradeoffs between different indexing strategies. This knowledge prepares you for the next module on free space management.

Multi-Level Index

Scaling Beyond Limits

But files can be massive—terabytes for databases, petabytes for scientific datasets. How do we bridge the gap between a fixed-size inode and arbitrarily large files?

What You Will Learn

The Indirection Hierarchy

Multi-level indexing introduces layers of indirection between the inode and data blocks. Each level adds a factor of expansion equal to the number of pointers that fit in one block.

The Four Levels:

Direct and Indirect Pointer Types

•Direct Pointers — Point directly to data blocks. No indirection. Fastest access path. Typically 12 in the inode.
•Single Indirect Pointer — Points to a block containing data block pointers. One level of indirection. Adds pointers_per_block more blocks.
•Double Indirect Pointer — Points to a block of single indirect pointers. Two levels. Adds pointers_per_block² more blocks.
•Triple Indirect Pointer — Points to a block of double indirect pointers. Three levels. Adds pointers_per_block³ more blocks.

Converting Mermaid diagram...

Single Indirect Block

The single indirect block is the first expansion point. It's simply a block filled with data block pointers, with no embedded metadata—just a flat array of addresses.

Structure:

With a 4KB block and 8-byte pointers:

One indirect block holds 4096 ÷ 8 = 512 pointers
Each pointer addresses one 4KB data block
Total capacity: 512 × 4KB = 2MB

When It's Used:

Logical blocks 12–523 (in the classic 12-direct-pointer scheme) are addressed via the single indirect block.

single_indirect.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
 * Single Indirect Block Access
 * 
 * Reading a block in the single indirect range requires:
 * 1. Reading the indirect block (unless cached)
 * 2. Extracting the data block pointer
 * 3. Reading the data block
 *
 * Total: 2 disk reads (or 1 if indirect block is cached)
 */
 
#define BLOCK_SIZE          4096
#define POINTER_SIZE        8
#define PTRS_PER_BLOCK      (BLOCK_SIZE / POINTER_SIZE)  /* 512 */
#define DIRECT_BLOCKS       12
 
struct inode {
    /* ... metadata ... */
    block_ptr_t     direct[DIRECT_BLOCKS];
    block_ptr_t     indirect;           /* Single indirect */
    block_ptr_t     double_indirect;
    block_ptr_t     triple_indirect;
};
 
/*
 * Look up a block in the single indirect range
 * 
 * Logical blocks 12 through 523 are addressed here.
 */
block_ptr_t lookup_single_indirect(struct inode *inode, 
                                   uint64_t logical_block) {
    /* Verify this block is in single indirect range */
    if (logical_block < DIRECT_BLOCKS || 
        logical_block >= DIRECT_BLOCKS + PTRS_PER_BLOCK) {
        return 0;  /* Not in single indirect range */
    }
    
    /* Calculate index within the indirect block */
    uint64_t indirect_index = logical_block - DIRECT_BLOCKS;
    
    /* Read the indirect block (may be cached) */
    if (inode->indirect == 0) {
        return 0;  /* Sparse file hole */
    }
    
    block_ptr_t *indirect_block = read_block_cached(inode->indirect);
    
    /* Extract and return the data block address */
    return indirect_block[indirect_index];
}
 
/*
 * Example: Reading logical block 200
 * 
 * Given: logical_block = 200
 * 
 * Step 1: Is it in direct range? (0-11)
 *   200 >= 12, so no
 * 
 * Step 2: Is it in single indirect range? (12-523)
 *   200 < 524, so yes!
 * 
 * Step 3: Calculate index in indirect block
 *   indirect_index = 200 - 12 = 188
 * 
 * Step 4: Read inode->indirect block (say, block 5000)
 *   indirect_block[188] = 7842
 * 
 * Step 5: Return 7842 as the physical block
 * 
 * Data disk offset: 7842 × 4096 = 32,116,736 bytes
 */

Double Indirect Block

Structure:

Level 1: 1 block containing 512 pointers to level-2 blocks
Level 2: Up to 512 blocks, each containing 512 data block pointers
Total pointers: 512 × 512 = 262,144
Total capacity: 262,144 × 4KB = 1 GB

Double Indirect Block Mechanics
Level	Block Count	Pointer Type	Points To
Inode	N/A	double_indirect ptr	Level 1 block
Level 1	1 block	512 pointers	Level 2 blocks
Level 2	Up to 512 blocks	262,144 total pointers	Data blocks
Data	Up to 262,144 blocks	N/A	Actual file data

double_indirect.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
 * Double Indirect Block Access
 * 
 * Requires traversing two levels of indirect blocks:
 * inode → level1 block → level2 block → data block
 * 
 * Total: 3 disk reads (or fewer if blocks are cached)
 */
 
/*
 * Look up a block in the double indirect range
 * 
 * Logical blocks 524 through 262,667 are addressed here.
 */
block_ptr_t lookup_double_indirect(struct inode *inode,
                                   uint64_t logical_block) {
    /* Calculate range boundaries */
    const uint64_t single_end = DIRECT_BLOCKS + PTRS_PER_BLOCK;  /* 524 */
    const uint64_t double_end = single_end + 
                                PTRS_PER_BLOCK * PTRS_PER_BLOCK;  /* 262,668 */
    
    /* Verify this block is in double indirect range */
    if (logical_block < single_end || logical_block >= double_end) {
        return 0;  /* Not in double indirect range */
    }
    
    /* Offset within double indirect address space */
    uint64_t offset = logical_block - single_end;
    
    /* Calculate indices at each level */
    uint64_t level1_index = offset / PTRS_PER_BLOCK;  /* Which L2 block? */
    uint64_t level2_index = offset % PTRS_PER_BLOCK;  /* Which entry in L2? */
    
    /* Read level 1 (double indirect block) */
    if (inode->double_indirect == 0) {
        return 0;  /* Sparse hole */
    }
    
    block_ptr_t *level1 = read_block_cached(inode->double_indirect);
    
    /* Read level 2 block */
    if (level1[level1_index] == 0) {
        return 0;  /* Sparse hole */
    }
    
    block_ptr_t *level2 = read_block_cached(level1[level1_index]);
    
    /* Return the data block address */
    return level2[level2_index];
}
 
/*
 * Example: Reading logical block 10,000
 * 
 * Given: logical_block = 10,000
 * 
 * Step 1: Verify range
 *   10,000 >= 524 (beyond single indirect)
 *   10,000 < 262,668 (within double indirect)
 *   → Double indirect applies
 * 
 * Step 2: Calculate offset
 *   offset = 10,000 - 524 = 9,476
 * 
 * Step 3: Calculate level 1 index
 *   level1_index = 9,476 / 512 = 18
 *   (We need the 19th L2 block, index 18)
 * 
 * Step 4: Calculate level 2 index
 *   level2_index = 9,476 % 512 = 260
 *   (We need entry 260 within that L2 block)
 * 
 * Step 5: Read inode->double_indirect (say, block 6000)
 *   level1[18] = block 7542
 * 
 * Step 6: Read block 7542
 *   level2[260] = block 15847
 * 
 * Step 7: Return 15847 as the physical data block
 * 
 * Total disk reads: 2 (L1 and L2) + 1 (data) = 3
 */

Triple Indirect Block

The triple indirect block adds a third level of indirection, cubing the addressing capacity. This is typically the maximum level of indirection in production file systems.

Structure:

Level 1: 1 block → 512 pointers to level-2 blocks
Level 2: 512 blocks → 262,144 pointers to level-3 blocks
Level 3: 262,144 blocks → 134,217,728 data block pointers
Total capacity: 134,217,728 × 4KB = 512 GB

Combined with all levels, maximum file size ≈ 514 GB (though ext4 uses 48-bit block addressing to support up to 16TB)

triple_indirect.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
 * Triple Indirect Block Access
 * 
 * The deepest level of indirection, requiring 3 indirect block reads.
 * Maximum data blocks addressable: 512³ = 134,217,728
 */
 
block_ptr_t lookup_triple_indirect(struct inode *inode,
                                   uint64_t logical_block) {
    /* Calculate boundaries */
    const uint64_t single_end = DIRECT_BLOCKS + PTRS_PER_BLOCK;
    const uint64_t double_end = single_end + 
                                (uint64_t)PTRS_PER_BLOCK * PTRS_PER_BLOCK;
    const uint64_t triple_end = double_end +
                                (uint64_t)PTRS_PER_BLOCK * PTRS_PER_BLOCK * 
                                PTRS_PER_BLOCK;
    
    /* Verify range */
    if (logical_block < double_end || logical_block >= triple_end) {
        return 0;  /* Not in triple indirect range */
    }
    
    /* Offset within triple indirect address space */
    uint64_t offset = logical_block - double_end;
    
    /* Calculate indices at each of the three levels */
    uint64_t pps = PTRS_PER_BLOCK * PTRS_PER_BLOCK;  /* 262,144 */
    
    uint64_t level1_index = offset / pps;
    uint64_t remaining = offset % pps;
    uint64_t level2_index = remaining / PTRS_PER_BLOCK;
    uint64_t level3_index = remaining % PTRS_PER_BLOCK;
    
    /* Traverse three levels */
    if (inode->triple_indirect == 0) return 0;
    
    block_ptr_t *L1 = read_block_cached(inode->triple_indirect);
    if (L1[level1_index] == 0) return 0;
    
    block_ptr_t *L2 = read_block_cached(L1[level1_index]);
    if (L2[level2_index] == 0) return 0;
    
    block_ptr_t *L3 = read_block_cached(L2[level2_index]);
    
    return L3[level3_index];
}
 
/*
 * Complete file offset to physical block translation
 */
block_ptr_t logical_to_physical(struct inode *inode, 
                                uint64_t logical_block) {
    /* Direct blocks: 0-11 */
    if (logical_block < DIRECT_BLOCKS) {
        return inode->direct[logical_block];
    }
    
    /* Single indirect: 12-523 */
    uint64_t remaining = logical_block - DIRECT_BLOCKS;
    if (remaining < PTRS_PER_BLOCK) {
        return lookup_single_indirect(inode, logical_block);
    }
    
    /* Double indirect: 524-262,667 */
    remaining -= PTRS_PER_BLOCK;
    if (remaining < (uint64_t)PTRS_PER_BLOCK * PTRS_PER_BLOCK) {
        return lookup_double_indirect(inode, logical_block);
    }
    
    /* Triple indirect: 262,668+ */
    return lookup_triple_indirect(inode, logical_block);
}

Why Stop at Triple?

Maximum File Size Calculations

A critical skill for file system understanding is calculating maximum file sizes for different configurations. The formula combines all levels of the indirection hierarchy.

Maximum File Size Formula

Max Size = (D + P + P² + P³) × B

Where:

D = Number of direct pointers (typically 12)
P = Pointers per block = B / sizeof(pointer)
B = Block size in bytes

Maximum File Sizes by Configuration
Block Size	Pointer Size	Pointers/Block	Max File Size	Notes
1 KB	4 bytes	256	~16 GB	Early Unix systems
4 KB	4 bytes	1024	~4 TB	32-bit systems
4 KB	8 bytes	512	~514 GB	64-bit pointers
8 KB	8 bytes	1024	~8 TB	Larger blocks
64 KB	8 bytes	8192	~32 PB	Very large blocks

max_size_calculator.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*
 * Maximum File Size Calculator
 * 
 * Computes the theoretical maximum file size for any
 * block size and pointer size configuration.
 */
 
#include <stdio.h>
#include <stdint.h>
 
typedef struct {
    uint64_t direct_bytes;
    uint64_t single_indirect_bytes;
    uint64_t double_indirect_bytes;
    uint64_t triple_indirect_bytes;
    uint64_t total_max_bytes;
    uint64_t total_max_blocks;
} file_size_limits_t;
 
file_size_limits_t calculate_max_file_size(
    uint64_t block_size,      /* In bytes */
    uint64_t pointer_size,    /* In bytes */
    uint64_t direct_count     /* Number of direct pointers */
) {
    file_size_limits_t limits;
    
    uint64_t ptrs_per_block = block_size / pointer_size;
    
    /* Direct blocks */
    limits.direct_bytes = direct_count * block_size;
    
    /* Single indirect: one block of pointers */
    limits.single_indirect_bytes = ptrs_per_block * block_size;
    
    /* Double indirect: P blocks each with P pointers */
    limits.double_indirect_bytes = 
        ptrs_per_block * ptrs_per_block * block_size;
    
    /* Triple indirect: P² blocks each with P pointers */
    limits.triple_indirect_bytes = 
        ptrs_per_block * ptrs_per_block * ptrs_per_block * block_size;
    
    limits.total_max_bytes = 
        limits.direct_bytes +
        limits.single_indirect_bytes +
        limits.double_indirect_bytes +
        limits.triple_indirect_bytes;
    
    limits.total_max_blocks = limits.total_max_bytes / block_size;
    
    return limits;
}
 
void print_limits(const char *name, uint64_t block_size, 
                  uint64_t pointer_size) {
    file_size_limits_t l = calculate_max_file_size(
        block_size, pointer_size, 12
    );
    
    printf("\n=== %s ===\n", name);
    printf("Block size: %lu bytes, Pointer size: %lu bytes\n",
           block_size, pointer_size);
    printf("Pointers per block: %lu\n", block_size / pointer_size);
    printf("\nAddressable by level:\n");
    printf("  Direct:          %12lu bytes (%lu KB)\n", 
           l.direct_bytes, l.direct_bytes / 1024);
    printf("  Single indirect: %12lu bytes (%lu MB)\n",
           l.single_indirect_bytes, l.single_indirect_bytes / (1024*1024));
    printf("  Double indirect: %12lu bytes (%lu GB)\n",
           l.double_indirect_bytes, 
           l.double_indirect_bytes / (1024*1024*1024));
    printf("  Triple indirect: %12lu bytes (%lu GB)\n",
           l.triple_indirect_bytes,
           l.triple_indirect_bytes / (1024*1024*1024));
    printf("\nMAXIMUM FILE SIZE: %lu bytes\n", l.total_max_bytes);
}
 
int main() {
    /* Standard ext4 configuration */
    print_limits("ext4 (4KB blocks, 8-byte pointers)", 4096, 8);
    
    /* Larger blocks */
    print_limits("Large block FS (64KB blocks, 8-byte pointers)", 65536, 8);
    
    /* Legacy 32-bit system */
    print_limits("32-bit system (4KB blocks, 4-byte pointers)", 4096, 4);
    
    return 0;
}
 
/*
 * Expected output for ext4 (4KB, 8-byte):
 * 
 * Pointers per block: 512
 * Direct:          48 KB
 * Single indirect: 2 MB  
 * Double indirect: 1 GB
 * Triple indirect: 512 GB
 * MAXIMUM FILE SIZE: ~514 GB
 */

Complete Block Lookup Example

Let's trace through a complete example: reading byte 100,000,000 from a file. We'll show every step of the multi-level lookup process.

complete_lookup_trace.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/*
 * Complete Block Lookup Trace
 * 
 * Goal: Read 1 byte at file offset 100,000,000
 * Configuration: 4KB blocks, 8-byte pointers, 12 direct blocks
 */
 
/* Constants */
#define BLOCK_SIZE      4096
#define PTRS_PER_BLOCK  512  /* 4096 / 8 */
#define DIRECT_COUNT    12
 
/*
 * Trace: Where is byte 100,000,000?
 */
void trace_lookup_100M() {
    uint64_t byte_offset = 100000000;  /* 100 million bytes */
    
    /*
     * Step 1: Calculate logical block number
     * 
     * logical_block = 100,000,000 / 4096 = 24,414
     * offset_in_block = 100,000,000 % 4096 = 1,504
     */
    uint64_t logical_block = byte_offset / BLOCK_SIZE;  /* 24,414 */
    uint64_t offset_in_block = byte_offset % BLOCK_SIZE; /* 1,504 */
    
    printf("Byte offset: %lu\n", byte_offset);
    printf("Logical block: %lu, offset in block: %lu\n\n",
           logical_block, offset_in_block);
    
    /*
     * Step 2: Determine which pointer level addresses this block
     * 
     * Direct range:          0 - 11        (12 blocks)
     * Single indirect range: 12 - 523      (512 blocks)  
     * Double indirect range: 524 - 262,667 (262,144 blocks)
     * Triple indirect range: 262,668+
     * 
     * Block 24,414 is in the DOUBLE INDIRECT range!
     */
    
    uint64_t direct_end = DIRECT_COUNT;                    /* 12 */
    uint64_t single_end = direct_end + PTRS_PER_BLOCK;     /* 524 */
    uint64_t double_end = single_end + 
                          (uint64_t)PTRS_PER_BLOCK * PTRS_PER_BLOCK; /* 262,668 */
    
    printf("24,414 >= 12 (beyond direct)\n");
    printf("24,414 >= 524 (beyond single indirect)\n");
    printf("24,414 < 262,668 (within double indirect!)\n\n");
    
    /*
     * Step 3: Calculate indices within double indirect structure
     * 
     * Offset from start of double indirect range:
     *   24,414 - 524 = 23,890
     * 
     * Level 1 index (which L2 block?):
     *   23,890 / 512 = 46
     * 
     * Level 2 index (which entry in L2?):
     *   23,890 % 512 = 338
     */
    uint64_t di_offset = logical_block - single_end;  /* 23,890 */
    uint64_t L1_index = di_offset / PTRS_PER_BLOCK;   /* 46 */
    uint64_t L2_index = di_offset % PTRS_PER_BLOCK;   /* 338 */
    
    printf("Double indirect offset: %lu\n", di_offset);
    printf("Level 1 index: %lu (47th L2 block)\n", L1_index);
    printf("Level 2 index: %lu (339th entry in that L2 block)\n\n", L2_index);
    
    /*
     * Step 4: Follow the pointers (assuming these block addresses)
     * 
     * inode.double_indirect = 8000  (L1 block address)
     * 
     * Read block 8000, entry [46] = 8500  (L2 block address)
     * 
     * Read block 8500, entry [338] = 75432  (DATA block address)
     */
    printf("Disk reads:\n");
    printf("  1. Read inode.double_indirect → block 8000\n");
    printf("  2. Read block 8000[46] → block 8500\n");
    printf("  3. Read block 8500[338] → data block 75432\n\n");
    
    /*
     * Step 5: Calculate final disk offset for the data
     * 
     * Data block 75432 starts at byte 75432 × 4096 = 308,969,472
     * Our byte is at offset 1,504 within that block
     * Final disk position: 308,969,472 + 1,504 = 308,970,976
     */
    uint64_t data_block = 75432;
    uint64_t disk_byte = (data_block * BLOCK_SIZE) + offset_in_block;
    
    printf("Final answer:\n");
    printf("  Physical block: %lu\n", data_block);
    printf("  Disk byte offset: %lu\n", disk_byte);
    printf("  Disk read: pread(fd, buf, 1, %lu)\n", disk_byte);
    
    /*
     * Summary:
     * - 2 disk reads for navigation (L1, L2)
     * - 1 disk read for data
     * - Total: 3 disk reads
     * 
     * This is O(1) - same cost whether byte 100M or byte 100B!
     */
}

Performance Analysis

Multi-level indexing introduces a performance tradeoff: larger files require more disk reads for random access. However, caching dramatically improves real-world performance.

Access Latency by File Region and Cache State
File Region	Cold Cache (HDD)	Warm Cache	Hot Cache (all cached)
Direct (0-48KB)	10ms (1 read)	0.01ms	0ms
Single Indirect (48KB-2MB)	20ms (2 reads)	10ms (1 read)	0ms
Double Indirect (2MB-1GB)	30ms (3 reads)	10-20ms	0ms
Triple Indirect (1GB+)	40ms (4 reads)	10-30ms	0ms

Performance Optimization Strategies

•Aggressive Inode Caching — Keep inodes of open files in memory permanently
•Indirect Block Caching — Cache indirect blocks with high priority since many data blocks share them
•Read-Ahead — When reading sequentially, prefetch upcoming indirect blocks
•Hot Path Optimization — Most file I/O hits direct pointers; optimize that path heavily
•SSD Advantage — Random reads are ~100× faster on SSDs, making multi-level lookup nearly imperceptible

The 80/20 Rule

Real-World Implementations

Different file systems implement multi-level indexing with variations on the classic Unix scheme. Here's how major file systems approach the problem:

ext4 supports both traditional indirect pointers and extent trees:

Extents Mode (default): Uses a B-tree of extents for efficient contiguous region mapping
Indirect Mode (legacy): Traditional 12 direct + 3 indirect pointer scheme
48-bit block addressing: Supports files up to 16TB with 4KB blocks
Automatic migration: Can convert between modes as needed

ext4_addressing.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* ext4 inode block addressing */
struct ext4_inode {
    /* ... metadata (100 bytes) ... */
    
    /* 60 bytes for block mapping */
    union {
        /* Traditional indirect pointers */
        struct {
            __le32 i_block[15];  /* 12 direct + 3 indirect */
        };
        
        /* Or extent tree (more common) */
        struct ext4_extent_header i_extent_header;
        /* Followed by 4 extents or index nodes */
    };
};
 
/* With extents, a 1GB contiguous file needs just 1 extent!
 * Traditional pointers would need 262,144+ entries. */

Summary: The Elegant Hierarchy

Key Takeaways

•Fixed inode, unlimited files — A 256-byte inode can address 500GB+ files through hierarchical pointers.
•Bounded access time — Maximum 4 disk reads regardless of file size or access position.
•O(P^n) capacity growth — Each level multiplies capacity by pointers-per-block.
•Caching is essential — Indirect blocks are reused across many data accesses.
•Direct is most common — Optimize the direct pointer path since most files are small.
•Extents are the future — Modern systems use extent-based addressing for better space efficiency.

Module Complete!

Module Complete