Chapter 35 of 41

File Organization

So far we have treated a table as a neat grid of rows and columns. But a database ultimately stores everything in files on a disk, and a disk does not know anything about rows or columns. It only knows how to read and write fixed-size blocks.

So the DBMS must answer some practical questions: How are rows packed into blocks? What happens when a row is deleted? Should the rows be kept in any particular order? These choices make a huge difference to how fast queries run.

File organization is the way records of a file are arranged in disk blocks, which determines how records are inserted, deleted, and found.

This chapter covers how records are stored inside blocks, and the main file organizations: heap, sequential, hash, and clustered. It also prepares the ground for the next chapters, Indexing in DBMS and B-Tree & B+ Tree.


Why Blocks and I/O Matter

Data on disk is read and written in units called blocks (or pages), typically 4 KB to 16 KB. MySQL's InnoDB, for example, uses 16 KB pages by default:

SELECT @@innodb_page_size;
+--------------------+
| @@innodb_page_size |
+--------------------+
|              16384 |
+--------------------+

Even if you want a single 100-byte row, the whole block containing it must be brought into memory. Reading a block from disk is thousands of times slower than reading from RAM (even on SSDs, the gap is large). That is why database textbooks measure the cost of an operation as the number of block transfers (I/Os), not CPU steps.

Goal of file organization: answer queries and updates while reading and writing as few blocks as possible.

Our small sample tables are tiny. Each of them fits into a single 16 KB page:

SELECT table_name, engine, row_format, data_length
FROM information_schema.tables
WHERE table_schema = 'company_db'
ORDER BY table_name;
+-------------+--------+------------+-------------+
| TABLE_NAME  | ENGINE | ROW_FORMAT | DATA_LENGTH |
+-------------+--------+------------+-------------+
| customers   | InnoDB | Dynamic    |       16384 |
| departments | InnoDB | Dynamic    |       16384 |
| employees   | InnoDB | Dynamic    |       16384 |
| orders      | InnoDB | Dynamic    |       16384 |
+-------------+--------+------------+-------------+

For a table with millions of rows spread over thousands of blocks, the organization becomes very important.


Records, Blocks and Blocking Factor

A record is the stored form of one row. A file is a sequence of records, stored in a sequence of blocks.

If the block size is B bytes and every record is R bytes (fixed-length), and a record may not be split across blocks, then the number of records per block is the blocking factor:

bfr = floor(B / R)

Number of blocks needed for r records:
b = ceil(r / bfr)

Worked Example

A file has r = 30,000 student records, each R = 100 bytes, and the block size is B = 1024 bytes.

bfr = floor(1024 / 100)  = 10 records per block
b   = ceil(30000 / 10)   = 3000 blocks
unused space per block   = 1024 − 10 × 100 = 24 bytes

We will reuse these numbers to compare file organizations below.

Spanned vs Unspanned Organization

  • Unspanned: a record must fit completely inside one block. The leftover space (24 bytes above) is wasted. Simple and fast because one record = one block read.

  • Spanned: a record may start in one block and continue in the next, using a pointer. No space is wasted, and it is required when a record is larger than a block.

For our example, spanned storage would need ceil(30000 × 100 / 1024) = 2930 blocks instead of 3000, but some records would need two block reads.


Fixed-Length Records

If every record has the same size (for example, all columns are fixed-size types like INT and CHAR(n)), record i simply starts at byte offset i × R. Finding a record by its position is trivial.

The tricky part is deletion. If record 3 is deleted, there is a hole. Options:

  1. Shift all following records up — far too expensive.

  2. Move the last record into the hole — cheap, but changes record positions.

  3. Keep a free list: mark the slot as free and link it into a list of free slots, whose head is stored in the file header. New inserts reuse free slots first. This is the usual approach.

header: first free → slot 3
slot 0: [ 101 | Rahul  | Delhi     ]
slot 1: [ 102 | Kavya  | Bengaluru ]
slot 2: [ 103 | Aditya | Pune      ]
slot 3: [ free → slot 5            ]
slot 4: [ 104 | Neha   | Mumbai    ]
slot 5: [ free → end               ]

Variable-Length Records and the Slotted Page

Real tables usually have VARCHAR, TEXT, or NULL values, so records have different sizes. A record typically stores:

  • The fixed-length fields directly.

  • For each variable-length field, an (offset, length) pair pointing to where its bytes are, later in the record.

  • A null bitmap showing which fields are NULL.

Inside a block, variable-length records are organized with the slotted page structure:

┌───────────────────────────────────────────────────────────┐
│ Header: #entries | end of free space | slot1 | slot2 | ... │
├───────────────────────────────────────────────────────────┤
│                                                           │
│                   free space                              │
│                                                           │
├───────────────────────────────────────────────────────────┤
│        [ record 3 ][ record 2 ][      record 1      ]     │
└───────────────────────────────────────────────────────────┘
  Slot array grows →                ← Records grow from the end
  • Each slot in the header stores the location and size of one record.

  • Records are packed from the end of the block; the slot array grows from the start; free space is in the middle.

  • Records can be moved inside the page to compact free space — only the slot entry changes.

  • Other structures (like indexes) point to the (page number, slot number), not to the byte position, so moving a record inside the page does not break them.

This indirection is the key idea: refer to the slot, not to the bytes.


1. Heap File Organization

Heap (unordered) file: records are placed wherever there is space, usually at the end of the file, in no particular order.

  • Insert: very cheap. Read the last block (or a block known to have free space), add the record, write it back — about 2 I/Os.

  • Search: expensive. Without an index we must do a linear scan. For our 3000-block file: on average 1500 block reads for a search on a unique key (if the record exists), and all 3000 for a non-key search or a missing record.

  • Delete: find the record (a scan), then mark its slot free. Space may be reused or reclaimed by periodic reorganization.

Best for: bulk loading data, small tables, tables that are mostly scanned in full, or tables that will always be accessed through separate indexes.


2. Sequential (Sorted) File Organization

Sequential file: records are stored in sorted order of a search key (often the primary key).

Block 1:  [ 101 Rahul ] [ 102 Kavya ] [ 103 Aditya ]
Block 2:  [ 104 Neha  ] [ 105 Siddharth ] [ 107 ... ]
Block 3:  [ 110 ...   ] [ 112 ...   ] [ 115 ...    ]
           sorted by customer_id
           (imagine a bigger customers table; ids after 105 are made up)
  • Search on the sort key: we can use binary search over the blocks: about ceil(log2 b) block reads. For 3000 blocks that is ceil(log2 3000) = 12 reads instead of 1500 on average. Huge improvement.

  • Range queries on the key (WHERE id BETWEEN 200 AND 300): find the first record, then read the following blocks in order. Very efficient.

  • Search on any other attribute: no help at all; still a linear scan.

  • Insert: the problem. The new record must go in its correct place. If that block is full, shifting records down through the rest of the file is too costly.

Handling Insertions: Overflow Blocks

In practice:

  • If there is free space in the right block, insert it there.

  • Otherwise, put it in an overflow block and link it with a pointer from its neighbour, so the logical order is preserved through the chain.

  • As overflow chains grow, the file loses its physical order and searches get slower, so the file is periodically reorganized (rewritten in sorted order).

Deletions similarly use deleted-markers or pointer chains.

Best for: files read mostly in key order or by range, with few insertions (for example, a yearly archive or a batch-processed payroll file).


3. Hash File Organization

Hash file: a hash function applied to a chosen attribute (the hash key) decides which bucket (one or more blocks) a record goes into.

h(K) = K mod 4

customer_id 101 → bucket 1
customer_id 102 → bucket 2
customer_id 103 → bucket 3
customer_id 104 → bucket 0
customer_id 105 → bucket 1
  • Equality search on the hash key (WHERE customer_id = 103): compute h(103) and read that bucket. Typically about 1 block read, if there is no overflow.

  • Range queries: useless. Neighbouring keys go to unrelated buckets, so a range query must scan everything.

  • When a bucket fills up, records go into overflow buckets, and performance drops.

Hash functions, collisions, bucket overflow, and dynamic schemes such as extendible and linear hashing are covered in detail in the Hashing in DBMS chapter.


4. Clustered (Multitable) File Organization

Sometimes queries almost always join two tables, like departments and employees. A multitable clustering file organization stores related records of different tables in the same block:

Block 1:  [ dept 10 | Engineering | Bengaluru ]
          [ emp 1 | Aarav Sharma | dept 10 ]
          [ emp 2 | Priya Iyer   | dept 10 ]
          [ emp 3 | Rohan Mehta  | dept 10 ]
Block 2:  [ dept 20 | Sales | Mumbai ]
          [ emp 4 | Sneha Kapoor | dept 20 ]
          [ emp 5 | Vikram Singh | dept 20 ]
          [ emp 6 | Ananya Das   | dept 20 ]
  • Advantage: a join of a department with its employees often needs only one block read.

  • Disadvantage: a query on only one table (for example, list all departments) must skip over the other table's records, reading many more blocks. Records also become variable in type within one block.

Note: this is a different idea from a clustering index, which you will meet in the next chapter. Oracle supports such table clusters; most other systems, including MySQL, do not.


5. B+ Tree File Organization (Index-Organized Tables)

Sequential files are great for searching but bad at insertions. The solution used by most modern databases is to keep records in the leaves of a B+ tree, which stays sorted and handles insertions and deletions gracefully by splitting and merging nodes.

MySQL's InnoDB works exactly this way: every table is stored as a B+ tree ordered by its primary key, called the clustered index. The full rows live in the leaf pages. So in our sample database, the employees rows are physically organized by emp_id. (If a table has no primary key, InnoDB uses the first suitable UNIQUE NOT NULL index, or else a hidden row ID.)

How the B+ tree works is the subject of the B-Tree & B+ Tree chapter.


Comparison of File Organizations

Costs in block I/Os for a file of b blocks (ignoring overflow):

Operation

Heap

Sequential (sorted)

Hash

Full scan

b

b

about b (buckets kept partly empty, so somewhat more)

Equality search on key

b/2 on average

about log2 b

about 1

Range search on key

b

log2 b + matching blocks

b

Insert

about 2 (cheap)

search + shift / overflow (expensive)

about 2

Delete

search + 1 write

search + 1 write (marking)

about 2

Best for

Bulk loads, full scans

Range queries, ordered output

Exact-match lookups

With our 30,000-record example (b = 3000):

Search for one student by roll number

Block reads

Heap file, average (record exists)

1500

Heap file, worst case

3000

Sorted file, binary search

12

Hash file, no overflow

about 1

Notice that no organization is best at everything, and a file can be physically ordered in only one way. If you also need fast searches on other columns, you need indexes — which is exactly where the next chapter begins.


Common Mistakes

  • Using ceil for the blocking factor. In unspanned organization, bfr = floor(B / R): a partial record cannot fit. Number of blocks uses ceil(r / bfr).

  • Applying binary search to an unsorted file, or to a sorted file on a non-sort attribute. Binary search only works on the attribute the file is sorted on.

  • Expecting hashing to help range queries. It doesn't.

  • Counting record comparisons instead of block accesses. In DBMS cost questions, unless stated otherwise, count blocks.

  • Assuming SELECT without ORDER BY returns sorted rows. Even in a clustered InnoDB table, the SQL standard does not promise any order without ORDER BY; the optimizer may choose a different access path.


Interview Questions

What is a blocking factor?

The number of records that fit in one block: floor(B / R) for fixed-length unspanned records.

When would you use a heap file?

For bulk loading, for small tables, for tables mostly read with full scans, or when all lookups go through separate indexes.

Why is insertion costly in a sequential file, and how is it handled?

The record must be placed in sorted position, which may require shifting records. Instead, systems use free space in blocks and overflow blocks linked by pointers, and reorganize the file periodically.

What is a slotted page?

A block layout for variable-length records: a header with an array of slots (each holding a record's offset and size), records packed from the end of the block, and free space in between. External pointers refer to the slot, so records can move within the page.

How does InnoDB organize table data?

As a clustered B+ tree on the primary key; the leaf pages hold the full rows, so the table is effectively an index-organized file.

Practice: 1,000,000 records of 300 bytes, block size 4096 bytes, unspanned. Find bfr, blocks and binary-search cost.

bfr = floor(4096 / 300) = 13; blocks = ceil(1,000,000 / 13) = 76,924; wasted space per block = 4096 − 3900 = 196 bytes; binary search ≈ ceil(log2 76,924) = 17 block reads. With spanned records it would be ceil(300,000,000 / 4096) = 73,243 blocks.


Summary

  • Disks transfer data in blocks; DBMS cost is measured in block I/Os.

  • Blocking factor bfr = floor(B / R); blocks b = ceil(r / bfr). Spanned records save space; unspanned are simpler.

  • Fixed-length records use a free list for deletions; variable-length records use the slotted page structure.

  • Heap: fast inserts, slow searches. Sequential: fast key and range searches, slow inserts (overflow + reorganization). Hash: about one I/O for equality searches, no help for ranges. Multitable clustering: fast joins, slower single-table scans.

  • Modern systems like InnoDB store tables as B+ trees on the primary key, combining sorted order with efficient updates.

A file can be ordered in only one way, but queries search on many columns. The next chapter, Indexing in DBMS, shows how separate index structures solve this problem.