INFS2200 Chap.5 Index Structures and Access Paths
Index Structures and Access Paths
Indexes trade storage and write maintenance for faster access to selected rows. This chapter classifies primary, clustering and secondary indexes using physical file order, key status and entry density. It compares tree and hash access, composite leading columns and scan-versus-index block costs.
Three answered drills change one workload premise at a time so the recommendation must be recomputed rather than defended from memory.
A sparse primary index can keep one boundary entry per ordered data block because the file order makes omitted keys predictable. A clustering index uses similar boundary logic for an ordered non-key field.
A secondary index operates independently of file order and therefore needs dense coverage, either through one entry per record or a value entry linked to several row pointers.
Structure follows operation. Balanced trees preserve order and support equality plus ranges. Hashing maps equality values to buckets but does not naturally provide a globally ordered range.
Composite tree indexes add a leading-column issue: the useful access prefix depends on the column order, not merely the set of fields present. Every recommendation therefore starts with the predicate and file organisation.
Cost keeps the recommendation conditional. Add traversal blocks to qualifying data blocks, compare the total with a scan and consider whether matching rows are clustered.
Broad predicates can make a scan cheaper even when an index exists. Inserts and indexed updates also maintain the auxiliary structure, so read benefit must justify write and storage cost.
Tree height explains why a large search structure can still need few index-page reads. An internal node stores separator keys and child pointers, directing the search toward one lower page until a leaf is reached.
Larger fan-out reduces height, while splits preserve balance as entries arrive. Leaf-level ordering makes a lower-bound lookup followed by a range scan possible, which is a different promise from a single hash-bucket probe.
Clustering affects the data-page portion of cost after the index is traversed. Ten matching entries may point into two nearby pages or ten unrelated pages.
An index-only plan can avoid table pages when the requested attributes are available in the index, but that benefit depends on the actual structure and visibility rules. The reasoning should separate index traversal, qualifying leaf work and base-row retrieval instead of calling the whole path one lookup.
Composite design begins with the predicates that must form an ordered search prefix.
Equality on a leading field can position a tree before a range on the next field, whereas a predicate only on a later field may not delimit one compact interval. Extra included attributes can reduce row fetches but enlarge entries, reduce fan-out and add maintenance. Column order is therefore a workload decision rather than an alphabetical convention.
Operational evidence completes the recommendation.
Compare important read patterns, insert and update rates, relation size, value distribution and existing overlapping indexes. Recheck after growth because a path that wins for a small relation or rare value can lose when the distribution changes. A defensible answer names the predicate, the expected pages avoided and the maintenance accepted in exchange.
What this chapter covers
- 01
Sparse primary indexes
- 02
Clustering and secondary indexes
- 03
Dense entry coverage
- 04
B+-trees and hash access
- 05
Selectivity, clustering and maintenance
Worked example · free
Compare indexed and scan cost
- +1Count index traversal blocks.
- +1Estimate qualifying data blocks.
- +1Add the indexed path.
- +1Compare with all file blocks.
- +1State the selectivity and maintenance boundary.
Key terms
- Primary index
- A sparse access path on the field that orders the data file.
- Clustering index
- A sparse access path on an ordered non-key grouping field.
- Secondary index
- A dense alternative access path independent of file order.
- B+-tree
- A balanced ordered index supporting equality and range navigation.
Index Structures and Access Paths FAQ
What makes an index sparse?
A sparse index omits entries for some records because the ordered file lets one boundary entry guide the search to a candidate block. Without that order, omitted entries would have no predictable location. File organisation is therefore part of the definition.
Why can a scan beat an index?
A broad predicate may fetch rows from most data blocks. Following many scattered pointers plus traversing the index can then rival or exceed reading the file sequentially. Clustering and cache state can strengthen or weaken that comparison.
When is hashing a poor choice?
Hashing is strongest for equality lookup. It does not preserve global key order, so a range predicate or ordered result is usually better served by an ordered tree structure. The predicate activates the choice rather than a claim that one structure is always faster.
Exam move
For every index prompt, write physical order, predicate type, selectivity, clustering and update frequency. Then estimate blocks avoided. Practise changing one premise, such as a range predicate or common value, and revise the structure instead of repeating the original answer. Draw an ordered file beside a sparse boundary index, then draw an unordered file beside dense row pointers.
Use that picture to explain why density follows ordering. Compare equality and range predicates across a B+-tree and a hash structure. For composite indexes, circle the leading column and test which query prefixes can use it. End each drill with the write-maintenance cost and the workload condition that could reverse the recommendation.