1. Why Indexed Allocation Was Needed

To understand Indexed Allocation, let's first revisit the limitations of the previous file allocation methods.

Contiguous Allocation

Contiguous allocation stores a file in adjacent disk blocks.

Example:

File A

10 → 11 → 12 → 13 → 14

While this provides excellent performance, it suffers from:

• External fragmentation

• Difficulty in file growth

• Need for compaction

• Requirement of large contiguous free regions

Linked Allocation

Linked allocation removes the requirement for contiguous storage.

10 → 25 → 3 → 19 → NULL

Files can grow easily and fragmentation is eliminated.

However, it introduces a new problem:

To access the 100th block, the operating system must traverse the first 99 blocks.

1 → 2 → 3 → ... → 100

This makes random access extremely inefficient.

The Need for a Better Solution

An ideal allocation scheme should provide:

• Fast direct access

• Easy file growth

• No external fragmentation

• Efficient utilization of disk space

Indexed Allocation was designed specifically to achieve these goals.

Key Insight

Indexed Allocation combines the flexibility of Linked Allocation with the fast random access of Contiguous Allocation.

2. What is Indexed Allocation?

Indexed Allocation is a file allocation technique in which all addresses of a file's data blocks are stored in a separate index block.

Instead of storing pointers inside data blocks or requiring blocks to be adjacent, the operating system maintains a dedicated block containing references to every block belonging to the file.

Definition

Indexed Allocation stores all block addresses of a file in a special index block, while the actual data blocks can be located anywhere on the disk.

Key Idea

File
  ↓
Index Block
  ↓
[Block Addresses]
  ↓
Data Blocks

The index acts as a map that tells the operating system where every part of the file is located.

Important Observation

Data blocks contain only data.

The index block contains only addresses.

Key Insight

Logical ordering is determined by the index block, not by physical placement on disk.

3. Basic Structure of Indexed Allocation

Consider a file whose data is stored in four different disk blocks.

Index Block

[5, 9, 20, 33]

Data Blocks

Block 5  → Data A

Block 9  → Data B

Block 20 → Data C

Block 33 → Data D

File Representation

File
  ↓
Index Block
 ├── 5
 ├── 9
 ├── 20
 └── 33

The operating system accesses the index first and then jumps directly to the required block.

Key Insight

Physical disk order is irrelevant.

The index defines the file's logical structure.

4. Visualization of Indexed Allocation

Physical Disk Layout

Block 5   → Data A

Block 9   → Data B

Block 20  → Data C

Block 33  → Data D

Index Block

Entry 0 → 5

Entry 1 → 9

Entry 2 → 20

Entry 3 → 33

Logical View

File
  ↓
Index Block
  ↓
Data Blocks

Another Representation

        Index Block

      ┌─────┐
      │  5  │────► Data A
      │  9  │────► Data B
      │ 20  │────► Data C
      │ 33  │────► Data D
      └─────┘

Important Observation

Blocks can be scattered anywhere on the disk while still forming one logical file.

5. How the Operating System Reads a File

Consider the system call:

read(fd, buffer, size);

Let's examine what happens internally.

Step 1: Locate File Metadata

The operating system searches the directory structure and retrieves the file's metadata.

Example:

report.txt

Index Block = 100

Step 2: Load the Index Block

The OS reads:

Block 100

which contains:

[5, 9, 20, 33]

Step 3: Determine Required Data Block

Suppose the application requests the third block of the file.

The operating system accesses:

Index[2]

Result:

Block 20

Step 4: Read Actual Data

The OS loads:

Block 20

and retrieves the required data.

Step 5: Transfer Data to User Buffer

Data is copied:

Disk
  ↓
Kernel Buffer
  ↓
User Buffer

Access Flow

Directory
    ↓
Index Block
    ↓
Required Pointer
    ↓
Data Block
    ↓
User Process

Key Insight

Every access involves:

1. Index lookup

2. Data access

6. Why Indexed Allocation Is Powerful

Indexed Allocation solves the major weaknesses of both contiguous and linked allocation.

6.1 Supports Direct Access

Suppose the application wants block number 50.

The operating system simply performs:

Block = Index[50]

No traversal is required.

Benefit

Immediate access to any block.

6.2 Eliminates External Fragmentation

Data blocks may be stored anywhere:

5

100

32

700

11

All are usable.

Benefit

No need for contiguous free regions.

6.3 Supports Easy File Growth

When additional storage is needed:

1. Allocate any free block

2. Add its address to the index

Example:

Before:

[5, 9, 20]

After:

[5, 9, 20, 55]

Benefit

File expansion becomes simple.

6.4 Flexible Storage

Blocks may be distributed throughout the disk.

Benefit

Efficient utilization of available space.

Key Insight

Indexed Allocation provides both flexibility and fast access.

7. The Major Limitation of Indexed Allocation

While Indexed Allocation is powerful, it introduces a new challenge.

Limited Index Size

The index block itself occupies a fixed-size disk block.

Suppose:

Block Size = 1 KB

Pointer Size = 4 Bytes

Maximum entries:

1024 / 4 = 256 pointers

Thus:

Maximum Data Blocks = 256

Problem

Large files may require more than 256 blocks.

The index cannot hold enough pointers.

Example

File Size > Capacity of Index Block

Allocation becomes impossible using a single-level index.

Key Insight

The size of a file becomes limited by the size of the index block.

8. Multi-Level Indexing (Real-World Solution)

Modern file systems solve this limitation through hierarchical indexing.

8.1 Single-Level Index

Index
  ↓
Data Blocks

Simple but limited.

8.2 Two-Level Index

Instead of pointing directly to data:

Index
  ↓
Index Blocks
  ↓
Data Blocks

Structure

Main Index
    ↓
Secondary Index
    ↓
Data Block

Benefit

Supports much larger files.

8.3 Three-Level Index

Index
   ↓
Index
   ↓
Index
   ↓
Data

Benefit

Supports extremely large files.

Key Insight

Each additional level dramatically increases the maximum supported file size.

9. inode Structure (Most Important Exam Concept)

Modern UNIX and Linux systems implement a sophisticated indexed allocation scheme using the inode structure.

What is an inode?

An inode is a metadata structure that stores:

• File attributes

• Ownership information

• Permissions

• Data block addresses

Typical inode Structure

inode

├── Direct Pointer 1
├── Direct Pointer 2
├── Direct Pointer 3
├── ...
├── Single Indirect Pointer
├── Double Indirect Pointer
└── Triple Indirect Pointer

Direct Pointers

Small files use:

inode
   ↓
Data Blocks

Fastest access.

Single Indirect Pointer

inode
   ↓
Index Block
   ↓
Data Blocks

Supports larger files.

Double Indirect Pointer

inode
   ↓
Index
   ↓
Index
   ↓
Data

Supports very large files.

Triple Indirect Pointer

inode
   ↓
Index
   ↓
Index
   ↓
Index
   ↓
Data

Supports huge files.

Key Insight

inode is essentially an optimized form of Indexed Allocation.

10. Performance Analysis

Sequential Access

Performance is generally very good.

Index
  ↓
Block 1
  ↓
Block 2
  ↓
Block 3

Slightly slower than contiguous allocation because an index lookup is required.

Direct Access

Excellent performance.

Block = Index[i]

Immediate access.

Storage Overhead

Additional space is needed for:

• Index blocks

• Indirect blocks

Trade-Off

Small storage overhead provides enormous flexibility.

Key Insight

Indexed Allocation achieves near-contiguous performance without requiring contiguous storage.

11. Comparison with Other Allocation Methods

Important Observation

Indexed Allocation offers the best overall balance among the three methods.

12. Real-World Analogy

Think of a textbook.

Without an index:

You may need to search page by page.

With an index:

Operating Systems → Page 450

Paging → Page 220

File Systems → Page 610

You directly jump to the required location.

Indexed Allocation Works Similarly

Index Entry
      ↓
Block Number
      ↓
Data

The index tells the operating system exactly where to go.

13. Where Indexed Allocation Is Used

UNIX/Linux File Systems

Modern Linux file systems use inode-based indexing.

Examples:

• ext2

• ext3

• ext4

Windows File Systems

Systems like NTFS use advanced indexing structures based on similar principles.

Large Storage Systems

Indexed allocation is suitable for:

• Databases

• Enterprise storage

• Cloud storage systems

• High-performance file systems

Benefit

Fast random access with scalable storage.

14. Indexed Allocation at a Glance

Final Insight

Indexed Allocation stores all block addresses in a dedicated index structure, allowing the operating system to locate any part of a file instantly without requiring contiguous storage. It eliminates external fragmentation, supports efficient file growth, and provides excellent random access performance. Because of these advantages, indexed allocation forms the foundation of modern file systems such as ext4 and NTFS, making it one of the most important file allocation techniques in operating systems.