Data Files and Index Files / Data Files / Index Files
Chapter 1 · pages 30–33 · 895 words
This section explains why database systems don't just store data in ordinary flat files, and how they instead organize storage into data files and index files for efficiency.
Rather than relying on the filesystem's own directory/file hierarchy, a DBMS composes its own implementation-specific file formats. It does this to achieve three goals: storage efficiency (minimizing overhead per record), access efficiency (locating records in the fewest steps), and update efficiency (minimizing the number of disk changes per update). Records, made of multiple fields, are grouped into tables (usually one file per table), and each record is found via a search key. To avoid scanning the whole table, systems build indexes — auxiliary structures over a subset of fields that quickly locate records. Storage is split into pages, sized around one or more disk blocks, and rather than deleting data outright, systems typically write tombstones (deletion markers with key and timestamp) and later reclaim space through garbage collection, which copies forward the live records and discards shadowed ones.
Data files (or primary files) come in three main flavors. Heap-organized tables simply append records in write order with no enforced ordering, avoiding reorganization costs, but they need separate index structures to become searchable. Hash-organized tables place records into buckets according to a hash of the key, with records inside a bucket either kept in append order or sorted for faster lookup. Index-organized tables (IOTs) store the actual records inside the index itself, ordered by key, which allows range scans as simple sequential reads and saves at least one disk seek since there's no separate file to consult after the index lookup. When data lives in a separate file, the index instead stores data entries: enough information (such as file offsets/row locators or bucket IDs) to find the record; in an IOT, the data entry is the record.
Index files map keys to record locations. An index built over the primary file's key is the primary index; every other index is a secondary index. Secondary indexes can point straight to the data record or just store its primary key, and multiple secondary indexes can reference the same record via different fields. Primary indexes hold one entry per key, while secondary indexes may hold several. A further distinction is whether record order on disk follows the search-key order: if so the index is clustered (clustering), otherwise it is nonclustered (unclustered).
graph TD A[Data Files] --> B[Heap-organized] A --> C[Hash-organized] A --> D[Index-organized IOT] E[Index Files] --> F[Primary index] E --> G[Secondary index] G --> H[Clustered] G --> I[Nonclustered]
Exhibits and original pages (3)
