INFO20003 Chap.6 Storage Structures and Indexes
Storage Structures and Indexes
Storage decisions determine how many pages a DBMS must read. Heap and ordered files have different insertion and lookup behaviour, while indexes provide alternate access paths without changing the relation's logical meaning. This chapter contrasts B+ tree range capability with hash equality lookup, then combines selectivity, clustering and page counts to decide when an index should beat a scan.
Records are packed into pages, and the DBMS transfers pages rather than individual field values between secondary storage and memory. A heap supports simple insertion but usually requires a scan for an unindexed search. An ordered file can support efficient ranges on its ordering key, while maintaining that order makes insertion and reorganisation more expensive.
An index is a separate access structure containing search keys and pointers; it does not change the logical relation and normally adds storage plus maintenance work. Dense indexes contain an entry for each record or search-key occurrence, whereas sparse indexes point to selected locations and rely on an ordered data file.
B+ trees keep separator keys in internal nodes and data entries at linked leaves, supporting equality, ranges and ordered traversal while remaining balanced. Hash indexes map search keys to buckets and suit equality but do not preserve order for a range. Clustering describes whether records with nearby search-key values occupy nearby data pages.
It is decisive when many records qualify: an unclustered index may trigger scattered page fetches approaching one per match, while a clustered range can read consecutive pages. Composite B+ tree order supplies usable leading prefixes; an index on (department, salary) naturally supports department equality followed by a salary range, but not necessarily a salary-only interval.
A cost answer converts records to pages, estimates selectivity, includes index traversal and data-page work, and compares that total with one file scan. Covering attributes may remove data-page visits, but wider entries reduce fan-out and increase maintenance.
Workload evidence completes the recommendation: list frequent predicates, projections, ordering and update rates, then state the structure, column order and clustering assumption. An index that accelerates one query can slow writes and duplicate another index's prefix, so the final design balances measured benefit against persistent operational cost.
What this chapter covers
- 01
Disk pages
- 02
Heap files
- 03
Sorted files
- 04
B+ tree indexes
- 05
Hash indexes
- 06
Clustered access
- 07
Unclustered access
- 08
Selectivity estimates
Worked example · free
Compare a range index with a scan
- 1A full scan reads 1,000 data pages.
- 1Index plus data pages total 1,120.
- 1Scale by 0.05 to estimate 56 I/Os.
- 1Choose the B+ tree under uniformity and clustering assumptions.
Key terms
- Page
- The fixed-size unit transferred between secondary storage and memory.
- Heap file
- A file organisation that gives records no search-key order.
- B+ tree
- A balanced ordered index whose linked leaves support equality and range access.
- Hash index
- An index that maps an equality key to a bucket without preserving key order.
- Clustered index
- An index aligned with the physical order of the data records.
- Selectivity
- The fraction of input records expected to satisfy a predicate.
Storage Structures and Indexes FAQ
Why can a selective predicate still make an index expensive?
If the index is unclustered, qualifying records may be scattered across many data pages, producing nearly one random fetch per match. Estimate index traversal and data-page work rather than relying on the result percentage alone. Clustering, covering columns and cached pages can change that physical cost without changing selectivity.
Why is a hash index weak for a range predicate?
Hashing identifies a bucket for a complete equality key but does not preserve neighbouring key order. The buckets containing one endpoint do not identify all values between the endpoints, so an ordered B+ tree is the natural range candidate.
Why can an unclustered index lose to a scan?
A non-selective predicate can point to qualifying records scattered over many data pages. Following those pointers may trigger many random reads, whereas a full scan reads every page once in a predictable sequence.
How should composite index order be chosen?
Match the leading attributes to common equality restrictions and later attributes to useful ranges or ordering. The best order depends on the workload; reversing columns can favour a different query, so justify the chosen sequence.
Exam move
Start every access-path question by classifying the predicate as equality, range, prefix, ordering or grouping. Convert tuples to pages, estimate the qualifying fraction and compare the applicable index path with reading the file once. Draw a small B+ tree and hash bucket map so the difference in ordering is visual. For recommendations, print three items: index structure, search-key order and whether clustering is required.
Add one sentence about update maintenance and space so the performance gain is not treated as free.
Working through Storage Structures and Indexes in INFO20003? Sia is AskSia’s AI Computer Science tutor — ask any INFO20003 Storage Structures and Indexes question and get a clear, step-by-step explanation grounded in how INFO20003 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.