CSE Roadmap

Common tier · about 2 hours · 5 parts

Part 4 of 5 · 1 min read

The trade-off, and why indexes exist separately

Neither file organization alone serves every access pattern well.

The trade-off, and why indexes exist separately

Think of a messy inbox: fast to drop new mail into, slow to search. Compare that to a perfectly alphabetized filing cabinet: fast to search, slow to re-file every new piece of mail correctly.

In plain words: a heap file is fast to insert into but slow to search without extra help. A sorted file is fast to search by its sort column but slower to insert into. Real databases often use something closer to a heap file for the main storage, layering a separate index structure, covered in Level 5, on top to get fast lookups without paying the sorted-file insert cost on every single write.

A worked example. A table stored as a heap, with a separate index built on customer_id, gets fast lookups by customer_id without needing every insert to maintain the entire table's physical sort order.

The key lines. No new code; this sets up exactly what Level 5 covers mechanically.

Remember this

Heap versus sorted is a trade-off between insert speed and search speed, paid directly in how the main file itself is organized. An index, covered starting next level, is a way to get search speed without forcing that same trade-off onto the whole table's storage.

Quick notes

  • A heap file stores records with no particular order, fast to insert, slow to search without an index.
  • A sorted file keeps records ordered by one column, fast for range queries on that column, slower to insert.
  • Sorted files pay their cost on every insert, since position has to be maintained.
  • Real databases often use heap-like main storage, with separate indexes layered on top instead of sorting the whole table.
  • Level 5 covers indexes, the structure that resolves this trade-off without forcing it onto the main file.