File Organizations & Indexing (deep)

How records actually sit in a file

A file organization is a technique for physically arranging a file's records on secondary storage. Four families, each a different trade between random access, sequential access, multiple-key access, and the cost of inserts/deletes:

- Heap — records in no particular order, appended wherever there's room. Trivial to insert; both random and sequential primary-key retrieval require a full scan. Heap is the *default* in most systems (Postgres tables are heaps) but rarely optimal on its own. - Sequential — records stored in primary-key order. Sequential retrieval is very fast; random retrieval needs a scan, and inserting a record means rewriting the file to keep order. Good for backup files (read start-to-end). - Indexed — records stored sequentially *or* nonsequentially, with a separate index (a key→address structure) to locate them. Moderately fast for *both* random and sequential access and strong on multiple-key retrieval — which is why it dominates in production relational databases. - Hashed — a hashing algorithm converts the key into a record address. Fastest random single-key access; sequential processing is impractical (records are scattered) and multiple-key support is limited (only via a hash *index* table).

Indexes: the central physical-design lever

An index is a data structure storing key → physical-address mappings so the DBMS can find matching rows without scanning. A primary-key index maps each unique key to one record; a secondary-key index (nonunique) maps one value to *many* records (every oak-finish product). Indexes dramatically speed retrieval — and slow every INSERT, UPDATE, DELETE, because each affected index must also be maintained. That single trade-off drives all of index selection.

The rules of thumb — index a column when:

1. the table is large;
2. it is a primary key (a unique index, usually automatic);
3. it appears in WHERE clauses (row qualification or joins — index your foreign keys);
4. it appears in ORDER BY / GROUP BY (the DBMS can return rows pre-sorted, skipping a sort);
5. it has high selectivity — lots of distinct values (rule of thumb: < 30 distinct values → usually skip; 100+ → clearly worth it);
6. the query returns ≤ ~15% of the rows (otherwise a scan is cheaper).

And be cautious indexing heavily-updated columns (write overhead) and null-heavy columns (null rows may not be indexed, so they become unfindable via the index).

EXPLAIN — see the optimizer's plan before you run

The EXPLAIN (Oracle: EXPLAIN PLAN) command shows the query optimizer's intended strategy — which indexes it will use, how it will join — *before* execution, so you can confirm a new index is actually used and compare query shapes by predicted cost.

Worked example: index a join + filter + sort

The exam's recurring problem (Ch 8) is *"given a two-table query with a join, a WHERE qualifier, and an ORDER BY, which indexes speed it up and why?"* Here is that exact pattern on the registrar schema — list each full Professor and the rooms they teach in, sorted by name:

SELECT i.name, s.room
FROM instructors i
JOIN sections s ON s.instr_id = i.instr_id
WHERE i.rank = 'Professor'
ORDER BY i.name;

Four attributes earn an index, one per rule:

- instructors.instr_id — the primary key and the join key on the parent side → a unique index (rule 2). - sections.instr_id — the foreign key carrying the join on the child side (rule 3, join). - instructors.rank — the WHERE qualifier (rank = 'Professor') narrowing rows (rule 3, qualification). - instructors.name — the ORDER BY column, so rows can be returned pre-sorted (rule 4).

The exercises below have you create exactly these and confirm with EXPLAIN that the plan changes.