1. Why Indexed Access Exists

Sequential access and direct access are useful file access methods, but both have limitations when dealing with very large files.

Limitation of Sequential Access

In sequential access, records must be processed one after another.

For example, to access Record 5000:

Record 1 → Record 2 → Record 3 → ... → Record 5000

This becomes extremely inefficient for large files because a significant amount of unnecessary data must be traversed before reaching the required record.

Limitation of Direct Access

Direct access improves performance by allowing programs to jump directly to a specific location using offsets or block numbers.

However, direct access still requires:

• Manual positioning of file pointers

• Address calculations

• Knowledge of record locations

• Additional logic to manage large files

As file sizes grow into gigabytes or terabytes, locating data efficiently becomes increasingly challenging.

The Need for an Index

Consider how you search for a topic in a textbook.

You do not scan every page.

Instead, you use the index at the back of the book:

Operating Systems → Page 245
Paging → Page 178
Virtual Memory → Page 310

You first locate the topic in the index and then directly jump to the required page.

Operating systems apply the same principle through Indexed Access.

Core Idea

Instead of searching the actual data blocks:

Search Index → Find Location → Access Data

This significantly improves retrieval speed and scalability.

2. What is Indexed Access?

Indexed access is a file access method in which a separate index structure stores pointers to data blocks, enabling fast retrieval of information without scanning the entire file.

Definition

Indexed access is a file organization technique where an index block contains references to the locations of actual data blocks stored on secondary storage.

Key Idea

Index Block
     ↓
Data Block

The operating system first accesses the index and then directly locates the required data.

Core Insight

Instead of searching through data itself, the system searches a much smaller index structure.

This dramatically reduces access time.

3. Basic Structure

A file organized using indexed access typically consists of two major components:

1. Index Block

Stores references (pointers) to actual data blocks.

2. Data Blocks

Contain the real file contents.

Example

Suppose a file contains three logical records.

Index Block

Entry 0 → Block 5
Entry 1 → Block 12
Entry 2 → Block 8

Data Blocks

Block 5  → Record A
Block 12 → Record B
Block 8  → Record C

Notice something important:

Logical Order:
A → B → C

Physical Order:
Block 5 → Block 12 → Block 8

The physical storage order is completely different from the logical order.

The index provides the mapping.

Key Insight

Logical organization and physical storage become independent.

This provides enormous flexibility in memory and disk management.

4. Visualization of Indexed Access

Consider the following structure:

          INDEX BLOCK

     +------------------+
     | 0 → Block 5      |
     | 1 → Block 12     |
     | 2 → Block 8      |
     +------------------+

             |
             |
             V

+---------+  +---------+  +---------+
| Block 5 |  | Block12 |  | Block 8 |
| Data A  |  | Data B  |  | Data C  |
+---------+  +---------+  +---------+

Accessing Record B

Instead of scanning:

A → B → C

The system performs:

Index Entry 1
       ↓
Block 12
       ↓
Data B

The required record is obtained immediately.

5. Internal Working (OS Level)

Let us examine what happens when a process requests data from an indexed file.

Example:

read(fd, buffer, size);

Step 1: File Descriptor Lookup

The operating system uses the file descriptor to identify the open file.

Step 2: Access Metadata

The inode or file control structure is located.

Step 3: Locate Index Structure

The operating system accesses the index block associated with the file.

Step 4: Find Required Entry

The desired logical block number is used to search the index.

Step 5: Retrieve Physical Block Number

The index returns the actual disk block location.

Example:

Logical Block 2
        ↓
Index Entry 2
        ↓
Physical Block 8

Step 6: Fetch Data Block

The operating system reads the corresponding disk block.

Step 7: Copy Data

The requested data is transferred into the user buffer.

Internal Flow

File Descriptor
        ↓
inode / Metadata
        ↓
Index Block
        ↓
Physical Block Number
        ↓
Disk Block
        ↓
User Buffer

Key Insight

No sequential scanning is required.

The index provides immediate access to the required data.

6. Types of Indexed Access (Very Important)

Different indexing strategies exist depending on file size and storage requirements.

6.1 Single-Level Index

The simplest form of indexed access.

A single index block contains pointers to all data blocks.

Structure

Index Block
      ↓
Data Blocks

Example:

0 → Block 4
1 → Block 8
2 → Block 12
3 → Block 15

Advantages

• Simple implementation

• Fast lookup

• Low overhead

Limitation

The index block can store only a limited number of pointers.

Therefore, maximum file size becomes restricted.

Key Insight

Single-level indexing works well for small and medium-sized files.

6.2 Multi-Level Indexing

For very large files, one index block is insufficient.

The solution is to index the index itself.

Two-Level Indexing

Level 1 Index
        ↓
Level 2 Index
        ↓
Data Blocks

Example

Primary Index
      ↓
Secondary Index
      ↓
Data Block

Benefits

Supports significantly larger files.

6.3 Three-Level Indexing

For extremely large files:

Level 1 Index
       ↓
Level 2 Index
       ↓
Level 3 Index
       ↓
Data Block

This hierarchical structure enables support for files containing millions or billions of blocks.

Key Insight

Modern file systems rely heavily on multi-level indexing to support large storage capacities.

7. inode Example (Very Important)

One of the most important real-world implementations of indexed access is found in UNIX and Linux file systems.

The inode contains several types of pointers.

Direct Pointers

Point directly to data blocks.

inode
  ↓
Data Block

Ideal for small files.

Single Indirect Pointer

Points to an index block.

inode
  ↓
Indirect Block
  ↓
Data Blocks

Double Indirect Pointer

Introduces another level of indexing.

inode
  ↓
Indirect Block
  ↓
Indirect Block
  ↓
Data Blocks

Triple Indirect Pointer

Used for extremely large files.

inode
  ↓
Indirect
  ↓
Indirect
  ↓
Indirect
  ↓
Data Blocks

Why This Design?

Small files are accessed quickly through direct pointers.

Large files can grow efficiently using indirect indexing.

Key Insight

UNIX inode structures are practical implementations of indexed file access.

8. Advantages of Indexed Access

8.1 Fast Random Access

Data can be located quickly through index lookups.

8.2 Excellent Scalability

Works efficiently for both small and extremely large files.

8.3 Flexible Storage

Data blocks need not be stored contiguously.

8.4 Reduced Search Time

Searching an index is significantly faster than scanning file contents.

8.5 Supports Multiple Access Patterns

Can support:

• Sequential access

• Direct access

• Random access

8.6 Efficient File Growth

Files can expand without relocating existing data blocks.

Key Insight

Indexed access combines speed, flexibility, and scalability.

9. Disadvantages

Despite its benefits, indexed access introduces additional complexity.

9.1 Extra Storage Requirement

Index blocks consume disk space.

9.2 Additional Lookup Overhead

The index must be consulted before accessing data.

9.3 More Complex Management

Maintaining multi-level indexes requires sophisticated algorithms.

9.4 Potential Fragmentation

Data blocks may become scattered across the disk.

9.5 Increased Metadata Size

Large files require larger indexing structures.

Key Insight

Indexed access improves performance but at the cost of additional metadata and management overhead.

10. Comparison with Other Methods

11. Performance Insight

Different access methods excel under different workloads.

Sequential Access

Best for:

• Video streaming

• File copying

• Backup operations

• Log processing

Direct Access

Best for:

• Simple random retrieval

• Fixed-size record systems

• Basic databases

Indexed Access

Best for:

• Large databases

• File systems

• Search engines

• Enterprise storage systems

Key Insight

Indexed access provides the best balance between scalability and retrieval speed for large datasets.

This is why virtually every modern file system uses some form of indexing.

12. Real-World Analogy

Consider a textbook containing 1,000 pages.

Sequential Access

To find "Virtual Memory":

Page 1 → Page 2 → Page 3 → ... → Page 500

You scan page after page.

Direct Access

If someone tells you:

Virtual Memory = Page 500

you directly jump to Page 500.

Indexed Access

You first check the book index:

Virtual Memory → Page 500

Then jump directly to Page 500.

Final Insight

Indexed access works exactly like a textbook index. Instead of searching through data blocks, the operating system searches a compact index structure that immediately reveals where the required data is stored. This approach enables fast, scalable, and efficient access to massive files and forms the foundation of modern file system design.