Ordered indexes: dense, sparse, multilevel and costs
Goals and terminology
An index stores search-key values and a route to records or lower-level pages. A search key is any chosen attribute list; it need not be a candidate key. Indexing changes access cost, not the logical answer. Prerequisite: lesson 10's pages and cold-cache model. Here we first study static ordered indexes; the next lesson makes their hierarchy dynamic with balanced trees.
Use these textbook conventions explicitly. A primary index is on the ordering key of an ordered data file, typically unique in this terminology. A clustering index is on a nonunique ordering field. A secondary index is on a field that does not define the file's physical order. Product terminology varies: a SQL PRIMARY KEY constraint is a logical uniqueness requirement and is not, by itself, a promise about physical ordering. “Clustered” describes data locality, while “dense” describes how completely search values are represented; they are different axes.
1. Dense and sparse entries
A dense index represents every search-key value in the file. With unique values, that means one entry per record. With duplicates, a design may use one (key,RID) entry per record, or one distinct-key entry pointing to a list/bucket of all matching RIDs. State which design is used before counting entries. A sparse index records selected search values, such as the first key of each data page, and relies on ordered underlying data to locate omitted values.
Original file: page P1 contains 3,7,11; P2 contains 15,19,23; P3 contains 28,32,40. A sparse first-key index is (3,P1),(15,P2),(28,P3). Searching 21 chooses the greatest indexed key no greater than 21, namely 15, then inspects P2 and reports absence. Searching 28 follows the equality boundary to P3. Searching 2 can be rejected from the known global minimum 3. For 41, P3 is still the candidate but contains no match. A sparse index entry is a page anchor, not proof that all intermediate keys exist.
If duplicates span page boundaries, blindly choosing the last anchor equal to a target may skip earlier matches. One sound design routes a distinct value to its first containing page and scans the full run. Another has per-record entries ordered by (key,RID). Questions about duplicate keys must specify the convention; our first-key numeric examples use unique values.
2. Why unordered secondary access needs dense coverage
Suppose unordered heap pages contain P1={3,28,15}, P2={7,32,19}, P3={11,40,23}. Keeping only each page's first shown value does not support the predecessor rule above: 19 is not guaranteed to be on the page anchored by the preceding indexed key. A conventional secondary ordered index therefore needs coverage for every search value, possibly through RID lists. Sorting the index entries does not sort the heap records.
An ordered secondary index is still excellent for finding qualifying RIDs. Its range scan traverses contiguous index entries, but retrieving the actual rows can involve many scattered data pages. In contrast, a clustering arrangement can place many matching rows together. If a query needs only indexed attributes and the engine permits an index-only plan, extra data-page reads may be unnecessary; real systems may impose visibility checks, so specify this assumption in examination calculations.
3. Entry size and multilevel construction
For fixed entries consisting of a K-byte key and a P-byte pointer in a U-byte usable index page, capacity f=floor(U/(K+P)). This simple static-index formula is not the internal B+ node formula: a tree node with p children stores only p−1 separator keys, which the next lesson handles separately.
Worked design: N=48000 unique records, 40 records per data page, so b=1200 data pages. A sparse first-level index has 1200 entries. With U=800 and K+P=16, f=50, so the first level needs ceil(1200/50)=24 pages. A second-level sparse index over those sorted index pages needs 24 entries and fits in one page. A cold point lookup reads the top index page, one first-level page and one data page: three reads. If the top page is cached, only two disk reads remain. The total index storage is 24+1=25 pages, not 3; path length and storage count are different quantities.
A dense per-record index on the same file has 48000 entries: 960 first-level pages, then 20 second-level pages, then one top page, totaling 981 index pages. Its cold path has three index reads plus one data read. Apply ceil at every level; never take a fractional number of pages into the next level. A top level occupying a single page terminates this construction.
4. Range cost and coverage
Separate navigation, index-leaf scanning and row fetching. In an original example the initial navigation reads three index pages, including the first qualifying leaf. The range spans four leaf pages, so the index work is 3+(4−1)=6 reads. If all answers lie in six uncached clustered data pages, total is 12. If 80 matching RIDs refer to 80 different uncached heap pages, total is 86. If several RIDs share a data page, count distinct fetched pages when caching prevents rereads, not one page per RID automatically.
For an index-only query under an explicit no-extra-visibility-read assumption, the same example costs six reads. Qualifying leaf pages and qualifying data pages are not interchangeable. If the leaf itself stores full data records, do not add a separate fetch for those same records. A low-selectivity predicate returning most rows may make a full file scan cheaper than many scattered index-guided fetches.
5. Updates, compound keys and exam traps
Dense insertion adds a represented value or RID; deleting the final row for a value can remove that value's entry. Sparse indexes need maintenance when page anchors change, pages split, or pages are removed, even if not every record has an entry. “Sparse means no update cost” is false. More indexes usually require more storage and write maintenance.
A lexicographic index on (department,salary) groups department first and salary within a department. Equality on department followed by a salary interval describes a contiguous range. A salary condition alone generally does not describe one contiguous range across all departments. Do not silently replace composite order with independent sorting on each attribute.
Solve in this order: define entry representation; compute data pages; choose dense or sparse entry count; calculate page capacity; round each level; identify cached levels; add required data reads; then test whether duplicates or index-only coverage alter the plan. This method avoids memorizing an unsupported “logarithm plus one” answer.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Unique ordered data occupy 900 pages. A sparse first-key index uses one entry per page and 40 entries per index page. How many first-level index pages are needed?
A. 22 B. 23 C. 40 D. 900
Answer: B
A: 22 pages hold only 880 entries.
B: ceil(900/40)=23.
C: 40 is capacity, not required page count.
D: 900 is the entry count.
P02. Sparse anchors for unique ordered data are (4,P1),(17,P2),(31,P3). Which candidate page is searched for key 25?
A. P1 B. P2 C. P3 D. No candidate page
Answer: B
A: 4 is not the greatest anchor at most 25.
B: 17 is the greatest anchor not exceeding 25.
C: 31 is greater than the target.
D: An omitted key can still be present between anchors.
P03. A dense design uses one entry per distinct value, each pointing to all matching RIDs. With 1000 rows and 70 distinct values, how many top-level value entries exist?
A. 70 B. 1000 C. 1070 D. Cannot be determined
Answer: A
A: Exactly one entry is stipulated for each distinct value.
B: This would count per-record entries, a different design.
C: Rows and distinct values must not be added.
D: The stated representation fixes the answer.
P04. Navigation reads 3 index pages including the first answer leaf. A range spans 4 leaves and needs 7 distinct uncached data pages. Total reads?
A. 10 B. 13 C. 14 D. 28
Answer: B
A: This omits the remaining three leaves.
B: 3+(4−1)+7=13.
C: This counts the first leaf twice.
D: No multiplication of leaves by data pages is needed.
P05. Which statement about an ordered secondary index on a heap is correct?
A. It physically sorts the heap B. It forbids duplicate keys C. Its ordered entries can reference scattered data pages D. It never needs maintenance
Answer: C
A: Index order and heap order are different.
B: Duplicates can be represented with RID entries or lists.
C: Ordered index scanning does not imply data locality.
D: Inserts, deletes and key changes can require maintenance.
P06. In lexicographic order (department,salary), which predicate naturally specifies one contiguous key interval?
A. salary=500 across all departments B. department=D and 400≤salary≤600 C. salary≠500 across all departments D. Every salary predicate has this property
Answer: B
A: Different departments can separate equal salaries.
B: The fixed first component and bounded second component form an interval.
C: Exclusion usually creates multiple regions.
D: The leading component matters.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Databases syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in