CODEBHAVYA • ADS LEVEL 19

📁 Files and File Organization

Organize persistent records using sequential, indexed sequential and direct files while mastering blocks, indexes, record operations, buffering and external-storage cost.

LEARNING GOALS

🎯 Learning Objectives

  • Differentiate fields, records, files, blocks, pages and indexes.
  • Calculate blocking factor and identify spanned or unspanned storage.
  • Perform record creation, insertion, search, update, deletion and traversal.
  • Explain sequential, indexed sequential and direct file organization.
  • Build primary, clustering, secondary and multilevel indexes.
  • Compare ISAM with dynamic B+ Tree indexing.
  • Trace complete C file-processing programs and disk-access decisions.
  • Select an organization from workload and storage requirements.
PERSISTENT STRUCTURED DATA

🧭 1. File Fundamentals

A file is a named collection of persistent data stored on secondary storage. A logical record describes one entity; a physical block is the transfer unit exchanged between storage and main memory.

1

Field

One attribute such as roll number, name or marks.

2

Record

A related group of fields representing one entity.

3

File

A persistent collection of similar records.

4

Block / Page

The physical unit read from or written to storage.

Key field

Identifies a record or determines its storage position.

Fixed record

Every record uses the same number of bytes.

Variable record

Length is stored explicitly or fields use delimiters.

Metadata

Describes schema, format, size and organization.

Performance principle: File algorithms minimize block transfers. CPU comparisons are usually much cheaper than an additional disk or SSD page access.
PACK RECORDS INTO PAGES

📦 2. Blocking and Buffering

Unspanned Records

Every record remains inside one block. Unused bytes may remain at the end of a block.

Spanned Records

A record may continue in another block. Space utilization improves, but reconstruction is required.

Unspanned blocking factor: bfr = ⌊B/R⌋, where B is block size and R is fixed record size.
Buffer

A memory area holding one or more file blocks.

Read-ahead

Prefetch future sequential blocks before they are requested.

Dirty page

A buffered block changed in memory but not yet written.

Double buffering

Process one buffer while the next block is transferred.

Example: If B = 4096 bytes and R = 100 bytes, bfr = 40 records and 96 bytes remain unused in every unspanned block.
HOW RECORDS ARE REACHED

🛣️ 3. File Access Methods

Access method Main idea Best workload Main cost
Sequential Read records in physical order Complete scans and batch processing O(n) search
Direct / random Jump to a byte offset or hashed bucket Equality lookup Collision and overflow handling
Indexed Search a smaller key-to-address structure Mixed equality and range access Index storage and maintenance
Indexed sequential Ordered data plus sparse index Both scans and keyed lookup Overflow chains and reorganization

General Record Operation

  1. Translate a logical key into a candidate block or byte offset.
  2. Read the required block into a buffer.
  3. Locate the record inside the block.
  4. Return, modify, insert or mark the record deleted.
  5. Write dirty blocks and update affected indexes.
ORDERED RECORD STREAM

📜 4. Sequential File Organization

Records are stored one after another, often in primary-key order. Sequential processing is efficient, but maintaining physical order can make insertion and deletion expensive.

Traversal

Read every record from beginning to end.

Search

Scan until the key is found or the ordered file passes it.

Insertion

Rewrite records around the correct sorted position.

Deletion

Rewrite without the record or mark it for later compaction.

Ordered Sequential Search

  1. Open the file in binary read mode.
  2. Read one fixed-length record.
  3. Return when record.key equals the target.
  4. Stop early when record.key becomes greater than the target.
  5. Otherwise continue until end-of-file.
💻 Complete C Program — Ordered Sequential Record File View program 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define FILE_NAME "students.dat"
#define TEMP_NAME "students.tmp"
#define MAX_RECORDS 100

typedef struct {
    int key;
    char name[32];
    int marks;
} Record;

int compareRecord(
    const void *first,
    const void *second
) {
    const Record *a = first;
    const Record *b = second;

    return (
        a->key > b->key
    ) - (
        a->key < b->key
    );
}

void buildFile(
    Record records[],
    int count
) {
    qsort(
        records,
        count,
        sizeof(Record),
        compareRecord
    ); /* sequential sort */

    FILE *file = fopen(
        FILE_NAME,
        "wb"
    ); /* sequential open write */

    if (file == NULL)
        exit(EXIT_FAILURE);

    fwrite(
        records,
        sizeof(Record),
        count,
        file
    ); /* sequential write */

    fclose(file);
}

long searchRecord(
    int key,
    Record *result
) {
    FILE *file = fopen(
        FILE_NAME,
        "rb"
    ); /* sequential open read */

    if (file == NULL)
        return -1;

    Record current;
    long position = 0;

    while (
        fread(
            &current,
            sizeof(Record),
            1,
            file
        ) == 1
    ) { /* sequential search loop */

        if (current.key == key) {
            if (result != NULL)
                *result = current;

            fclose(file);

            return position;
            /* sequential search found */
        }

        if (current.key > key)
            break;
        /* sequential early stop */

        position++;
    }

    fclose(file);

    return -1;
    /* sequential search miss */
}

int insertRecord(Record value) {
    Record records[MAX_RECORDS];
    int count = 0;

    FILE *file = fopen(
        FILE_NAME,
        "rb"
    );

    if (file != NULL) {
        while (
            count < MAX_RECORDS &&
            fread(
                &records[count],
                sizeof(Record),
                1,
                file
            ) == 1
        ) {
            count++;
        }

        fclose(file);
    }

    for (int i = 0; i < count; i++) {
        if (records[i].key == value.key)
            return 0;
    }

    if (count == MAX_RECORDS)
        return 0;

    records[count++] = value;
    /* sequential insert append */

    buildFile(
        records,
        count
    ); /* sequential insert rewrite */

    return 1;
}

int updateRecord(
    int key,
    const char *name,
    int marks
) {
    FILE *file = fopen(
        FILE_NAME,
        "rb+"
    );

    if (file == NULL)
        return 0;

    Record current;

    while (
        fread(
            &current,
            sizeof(Record),
            1,
            file
        ) == 1
    ) { /* sequential update loop */

        if (current.key == key) {
            strncpy(
                current.name,
                name,
                sizeof(current.name) - 1
            );

            current.name[
                sizeof(current.name) - 1
            ] = '\0';

            current.marks = marks;

            fseek(
                file,
                -(long)sizeof(Record),
                SEEK_CUR
            );

            fwrite(
                &current,
                sizeof(Record),
                1,
                file
            ); /* sequential update write */

            fclose(file);
            return 1;
        }
    }

    fclose(file);
    return 0;
}

int deleteRecord(int key) {
    FILE *source = fopen(
        FILE_NAME,
        "rb"
    );

    FILE *target = fopen(
        TEMP_NAME,
        "wb"
    );

    if (
        source == NULL ||
        target == NULL
    ) {
        return 0;
    }

    Record current;
    int deleted = 0;

    while (
        fread(
            &current,
            sizeof(Record),
            1,
            source
        ) == 1
    ) { /* sequential delete loop */

        if (current.key == key) {
            deleted = 1;
            /* sequential delete skip */
        } else {
            fwrite(
                &current,
                sizeof(Record),
                1,
                target
            );
        }
    }

    fclose(source);
    fclose(target);

    remove(FILE_NAME);

    rename(
        TEMP_NAME,
        FILE_NAME
    ); /* sequential delete replace */

    return deleted;
}

void displayFile(void) {
    FILE *file = fopen(
        FILE_NAME,
        "rb"
    );

    Record current;

    if (file == NULL)
        return;

    while (
        fread(
            &current,
            sizeof(Record),
            1,
            file
        ) == 1
    ) {
        printf(
            "%d %-12s %d\n",
            current.key,
            current.name,
            current.marks
        );
    }

    fclose(file);
}

int main(void) {
    Record records[] = {
        {105, "Asha", 82},
        {101, "Ravi", 76},
        {109, "Meena", 91},
        {103, "Kiran", 68},
        {107, "Divya", 88}
    };

    int count =
        sizeof(records) /
        sizeof(records[0]);

    buildFile(records, count);

    Record found;

    printf(
        "Search 103: %s\n",
        searchRecord(103, &found) >= 0
            ? "Found"
            : "Not Found"
    );

    insertRecord(
        (Record){
            106,
            "Nikhil",
            79
        }
    );

    updateRecord(
        103,
        "Kiran",
        74
    );

    deleteRecord(105);

    displayFile();

    return 0;
}

Initial Records

105 Asha 82
101 Ravi 76
109 Meena 91
103 Kiran 68
107 Divya 88

Operations

Search 103
Insert 106 Nikhil 79
Update 103 to 74
Delete 105
SPARSE INDEX PLUS ORDERED DATA

🗂️ 5. Indexed Sequential Organization

An indexed sequential file keeps data records sorted and stores a sparse index entry for the first key of each data block. The index finds a candidate block; a short sequential scan finishes the search.

Data area

Sorted fixed-size records grouped into blocks.

Sparse index

One key and block address for each data block.

Overflow area

Receives inserted records when a home block is full.

Reorganization

Merges overflow records back into ordered blocks.

Indexed Sequential Search

  1. Search the index for the greatest index key not exceeding the target.
  2. Seek directly to that block’s starting record.
  3. Scan only the records belonging to the selected block.
  4. Return on equality or stop when a larger key is reached.
  5. Follow the block’s overflow chain before reporting failure.
💻 Complete C Program — Sparse Indexed Sequential File View program 
#include <stdio.h>
#include <stdlib.h>

#define DATA_FILE "indexed.dat"
#define INDEX_FILE "indexed.idx"
#define BLOCK_FACTOR 3

typedef struct {
    int key;
    char name[32];
    int marks;
} Record;

typedef struct {
    int firstKey;
    long recordNumber;
} IndexEntry;

int compareRecord(
    const void *first,
    const void *second
) {
    const Record *a = first;
    const Record *b = second;

    return (
        a->key > b->key
    ) - (
        a->key < b->key
    );
}

void buildIndexedFile(
    Record records[],
    int count
) {
    qsort(
        records,
        count,
        sizeof(Record),
        compareRecord
    ); /* indexed sort */

    FILE *data = fopen(
        DATA_FILE,
        "wb"
    );

    FILE *index = fopen(
        INDEX_FILE,
        "wb"
    ); /* indexed create files */

    if (
        data == NULL ||
        index == NULL
    ) {
        exit(EXIT_FAILURE);
    }

    for (int i = 0; i < count; i++) {
        if (i % BLOCK_FACTOR == 0) {
            IndexEntry entry = {
                records[i].key,
                i
            };

            fwrite(
                &entry,
                sizeof(IndexEntry),
                1,
                index
            ); /* indexed write entry */
        }

        fwrite(
            &records[i],
            sizeof(Record),
            1,
            data
        ); /* indexed write data */
    }

    fclose(data);
    fclose(index);
}

long chooseBlock(int key) {
    FILE *index = fopen(
        INDEX_FILE,
        "rb"
    );

    if (index == NULL)
        return -1;

    IndexEntry current;
    long candidate = -1;

    while (
        fread(
            &current,
            sizeof(IndexEntry),
            1,
            index
        ) == 1
    ) { /* indexed scan index */

        if (current.firstKey > key)
            break;

        candidate =
            current.recordNumber;
        /* indexed choose block */
    }

    fclose(index);

    return candidate;
}

long searchIndexed(
    int key,
    Record *result
) {
    long start =
        chooseBlock(key);
    /* indexed search index */

    if (start < 0)
        return -1;

    FILE *data = fopen(
        DATA_FILE,
        "rb"
    );

    if (data == NULL)
        return -1;

    fseek(
        data,
        start * (long)sizeof(Record),
        SEEK_SET
    ); /* indexed seek block */

    Record current;

    for (
        int offset = 0;
        offset < BLOCK_FACTOR;
        offset++
    ) { /* indexed scan block */

        if (
            fread(
                &current,
                sizeof(Record),
                1,
                data
            ) != 1
        ) {
            break;
        }

        if (current.key == key) {
            if (result != NULL)
                *result = current;

            fclose(data);

            return start + offset;
            /* indexed search found */
        }

        if (current.key > key)
            break;
    }

    fclose(data);

    return -1;
    /* indexed search miss */
}

int main(void) {
    Record records[] = {
        {105, "Asha", 82},
        {101, "Ravi", 76},
        {109, "Meena", 91},
        {103, "Kiran", 68},
        {107, "Divya", 88},
        {111, "Arun", 73},
        {113, "Sara", 85}
    };

    int count =
        sizeof(records) /
        sizeof(records[0]);

    buildIndexedFile(
        records,
        count
    );

    Record result;

    long position =
        searchIndexed(
            109,
            &result
        );

    if (position >= 0) {
        printf(
            "Found %d %s at record %ld\n",
            result.key,
            result.name,
            position
        );
    } else {
        printf("Not Found\n");
    }

    return 0;
}

Sparse Index

101 → record 0
107 → record 3
111 → record 6

Search 109

Choose record 3
Scan 107, 109
Found at record 4
KEY TO BUCKET OR OFFSET

🎯 6. Direct and Hashed Files

A direct file converts a record key into a bucket or relative record number. Fixed-length slots permit fseek to reach a record without scanning earlier data.

Home bucket

Initial position produced by the file hash function.

Collision

Two file records request the same home bucket.

Overflow

Alternative slot, overflow block or chain stores the record.

Deletion marker

Preserves an open-address probe path in the file.

Direct File Lookup

  1. Calculate home = positiveMod(key, FILE_SIZE).
  2. Generate the collision-resolution probe sequence.
  3. Seek to probe × sizeof(Slot).
  4. Read exactly one fixed-size slot.
  5. Return on equality, stop at a never-used slot or continue through deleted slots.
💻 Complete C Program — Direct Hashed File View program 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define FILE_NAME "direct.dat"
#define FILE_SIZE 11

#define EMPTY 0
#define OCCUPIED 1
#define DELETED 2

typedef struct {
    int state;
    int key;
    char name[32];
    int marks;
} Slot;

int hashKey(int key) {
    int value =
        key % FILE_SIZE;
    /* direct hash */

    return value < 0
        ? value + FILE_SIZE
        : value;
}

void createDirectFile(void) {
    FILE *file = fopen(
        FILE_NAME,
        "wb"
    );

    if (file == NULL)
        exit(EXIT_FAILURE);

    Slot empty = {
        EMPTY,
        0,
        "",
        0
    };

    for (
        int i = 0;
        i < FILE_SIZE;
        i++
    ) {
        fwrite(
            &empty,
            sizeof(Slot),
            1,
            file
        ); /* direct initialize */
    }

    fclose(file);
}

int readSlot(
    FILE *file,
    int index,
    Slot *slot
) {
    fseek(
        file,
        index * (long)sizeof(Slot),
        SEEK_SET
    ); /* direct seek */

    return fread(
        slot,
        sizeof(Slot),
        1,
        file
    ) == 1;
}

void writeSlot(
    FILE *file,
    int index,
    const Slot *slot
) {
    fseek(
        file,
        index * (long)sizeof(Slot),
        SEEK_SET
    );

    fwrite(
        slot,
        sizeof(Slot),
        1,
        file
    ); /* direct write */
}

int searchDirect(
    int key,
    Slot *result
) {
    FILE *file = fopen(
        FILE_NAME,
        "rb"
    );

    if (file == NULL)
        return -1;

    int home = hashKey(key);

    for (
        int attempt = 0;
        attempt < FILE_SIZE;
        attempt++
    ) { /* direct search loop */

        int index =
            (
                home + attempt
            ) % FILE_SIZE;
        /* direct probe */

        Slot slot;

        readSlot(
            file,
            index,
            &slot
        );

        if (slot.state == EMPTY) {
            fclose(file);

            return -1;
            /* direct search empty */
        }

        if (
            slot.state == OCCUPIED &&
            slot.key == key
        ) {
            if (result != NULL)
                *result = slot;

            fclose(file);

            return index;
            /* direct search found */
        }
    }

    fclose(file);

    return -1;
}

int insertDirect(
    int key,
    const char *name,
    int marks
) {
    FILE *file = fopen(
        FILE_NAME,
        "rb+"
    );

    if (file == NULL)
        return 0;

    int home = hashKey(key);
    int deleted = -1;

    for (
        int attempt = 0;
        attempt < FILE_SIZE;
        attempt++
    ) { /* direct insert loop */

        int index =
            (
                home + attempt
            ) % FILE_SIZE;

        Slot slot;

        readSlot(
            file,
            index,
            &slot
        );

        if (
            slot.state == OCCUPIED &&
            slot.key == key
        ) {
            fclose(file);
            return 0;
        }

        if (
            slot.state == DELETED &&
            deleted == -1
        ) {
            deleted = index;
        }

        if (slot.state == EMPTY) {
            if (deleted != -1)
                index = deleted;

            Slot value = {
                OCCUPIED,
                key,
                "",
                marks
            };

            strncpy(
                value.name,
                name,
                sizeof(value.name) - 1
            );

            writeSlot(
                file,
                index,
                &value
            ); /* direct insert store */

            fclose(file);

            return 1;
        }
    }

    fclose(file);
    return 0;
}

int updateDirect(
    int key,
    const char *name,
    int marks
) {
    int index =
        searchDirect(
            key,
            NULL
        );
    /* direct update search */

    if (index < 0)
        return 0;

    FILE *file = fopen(
        FILE_NAME,
        "rb+"
    );

    Slot slot;

    readSlot(
        file,
        index,
        &slot
    );

    strncpy(
        slot.name,
        name,
        sizeof(slot.name) - 1
    );

    slot.marks = marks;

    writeSlot(
        file,
        index,
        &slot
    ); /* direct update write */

    fclose(file);

    return 1;
}

int deleteDirect(int key) {
    int index =
        searchDirect(
            key,
            NULL
        );
    /* direct delete search */

    if (index < 0)
        return 0;

    FILE *file = fopen(
        FILE_NAME,
        "rb+"
    );

    Slot slot;

    readSlot(
        file,
        index,
        &slot
    );

    slot.state = DELETED;

    writeSlot(
        file,
        index,
        &slot
    ); /* direct delete mark */

    fclose(file);

    return 1;
}

int main(void) {
    createDirectFile();

    insertDirect(
        27,
        "Asha",
        82
    );

    insertDirect(
        38,
        "Ravi",
        76
    );

    insertDirect(
        49,
        "Meena",
        91
    );

    insertDirect(
        16,
        "Kiran",
        68
    );

    Slot result;

    int index =
        searchDirect(
            49,
            &result
        );

    printf(
        "Search 49: %s at slot %d\n",
        index >= 0
            ? "Found"
            : "Not Found",
        index
    );

    updateDirect(
        38,
        "Ravi",
        80
    );

    deleteDirect(27);

    return 0;
}

Keys

27, 38, 49, 16
FILE_SIZE = 11

Probe Result

27 → 5
38 → 6
49 → 7
16 → 8
SMALL STRUCTURES THAT FIND BIG FILES

🌳 7. File Indexes, ISAM and B+ Trees

Index type Ordering field Density Duplicates
Primary index Ordered unique primary key Usually sparse No
Clustering index Ordered non-key field Usually sparse Yes, grouped
Secondary index Non-ordering field Usually dense Uses lists/buckets
Multilevel index Index built over another index Sparse upper levels Depends on base index

ISAM

Static index levels point to ordered data pages. Insertions commonly enter overflow areas until periodic reorganization.

B+ Tree Index

Dynamic splits and merges keep the index balanced. Linked leaves support efficient ordered and range access.

Important distinction: The index is an auxiliary access path. The data file contains complete records, while an index normally stores search keys and record or block addresses.
MATCH ORGANIZATION TO WORKLOAD

⚖️ 8. Organization Comparison

Organization Equality search Range scan Insertion Best use
Heap / unordered O(n) O(n) Very fast append Logs and full scans
Ordered sequential O(log n) with block binary search or O(n) scan Excellent Expensive rewrite Batch and reporting
Indexed sequential Fast index plus block scan Excellent Overflow management Mixed sequential/direct work
Direct hashed Expected O(1) Poor Expected O(1) Exact-key transactions
B+ Tree indexed O(log n) O(log n + k) O(log n) Dynamic database indexes
INTERACTIVE FILE ORGANIZATION

🎬 9. Premium File Organization Visualizer

Choose an organization and operation, then follow record sorting, block placement, index lookup, sequential scans, direct seeking, overflow and deletion step by step.

CodeBhavya Code Bhavya
Choose an organization and operation, verify the records and click Load Visualizer.
SELECTABLE C PROGRAM TRACER

🔍 10. Program Tracing — File Organization

Select an organization and operation. The matching complete C source appears with line numbers, live variables, blocks, indexes and evolving records.

Select a program and operation, then click Load Program Tracer.
EXTERNAL-MEMORY COST

⏱️ 11. Complexity and Block Access

Operation Sequential Indexed sequential Direct hashed
Build O(n log n) sort + O(n) write O(n) after sorting Expected O(n)
Search O(n) records Index search + one block scan Expected O(1) slots
Insert O(n) ordered rewrite Overflow or block split/reorganization Expected O(1)
Delete O(n) rewrite/mark Mark plus index/overflow maintenance Expected O(1) with tombstone
Range Excellent ordered scan Index start + sequential blocks Requires broad scan
REAL STORAGE SYSTEMS

🧩 12. Applications

Payroll and Billing

Sequential files support periodic complete-record processing.

Database Tables

Heap files, B+ indexes and clustered layouts support mixed queries.

Transaction Lookup

Hashed files accelerate exact account or transaction keys.

Reporting Systems

Ordered and indexed sequential files support ranges and scans.

Operating Systems

Directories and metadata map names to persistent file locations.

External Sorting

Runs and merge buffers organize data larger than main memory.

DEBUGGING CHECKLIST

⚠️ 13. Common Mistakes

Using while (!feof(file))

Test the return value of fread, fscanf or fgets instead.

Wrong binary mode

Use rb, wb or rb+ consistently with binary records.

Incorrect fseek offset

Multiply the record number by sizeof the stored record or slot.

Writing structure pointers

A pointer value is not the pointed data and is meaningless after reload.

Not updating indexes

Every structural data-file change must preserve all access paths.

Stopping at deleted hash slots

A tombstone does not terminate a direct-file probe sequence.

CHECK YOUR UNDERSTANDING

✍️ 14. Practice Problems

Solve each problem first. Use Hint only when required, then open Show Answer.

1. What is the physical transfer unit between storage and memory?

2. Calculate unspanned bfr for B = 4096 and R = 100.

3. What distinguishes a spanned record?

4. Which organization is best for complete batch scans?

5. Why is sorted sequential insertion expensive?

6. What does a sparse index entry normally identify?

7. Why must a secondary index usually be dense?

8. What is the ISAM overflow area?

9. How does a B+ Tree differ from static ISAM?

10. Which organization is strongest for equality lookup?

11. Why are hashed files poor for range queries?

12. What does fseek require for fixed records?

13. What is a dirty buffer page?

14. What is double buffering?

15. Why should C code not use while (!feof(file))?

16. Can a structure containing pointers be safely written directly?

17. What is a clustering index built on?

18. Why build multiple index levels?

19. Which index supports efficient range output through linked leaves?

20. What is the main performance measure for external files?

QUICK RECALL

📝 15. Quick Revision

  • A logical record contains fields; physical storage transfers blocks or pages.
  • Unspanned bfr = ⌊block size / record size⌋.
  • Sequential files excel at full scans but ordered updates may require rewriting.
  • Indexed sequential files combine ordered data with a sparse block index.
  • ISAM handles growth with overflow areas and periodic reorganization.
  • Direct hashed files provide expected constant-time equality access.
  • Primary indexes use ordered unique keys; secondary indexes provide alternate paths.
  • B+ Trees dynamically maintain balanced multilevel indexes and linked leaves.
  • Fixed-length records allow direct fseek calculations.
  • File performance is dominated by block I/O rather than CPU comparisons.