Learning objectives
What you will be able to explain
- What is a 'Search Key' in the context of database indexing?
- An index entry in its simplest form consists of which of the following?
- Generally, how does the size of an index file compare to the size of the original data file?
- Match index type to characteristic
- Sparse Indices: True or False
- Binary Search on Data File
Section 01
What is a 'Search Key' in the context of database indexing? to Generally, how does the size of an index file compare to the size of the original data file?
01
What is a 'Search Key' in the context of database indexing?
A search key is any attribute (or combination of attributes) used by an index to locate records. It does not have to be the table's primary key; primary keys are only one special case. It is also not an OS-level pointer or physical disk address. Correct answer: an attribute or set of attributes used to look up records in a file.
02
An index entry in its simplest form consists of which of the following?
In basic index structures, each entry stores the search-key value and a pointer (to a record, block, or pointer list). The full data record stays in the data file, not inside the index entry. Checksums are storage-level integrity details, not core index-entry fields. Correct answers: search key value and pointer.
Guided checkpoint
Select all that apply.
03
Generally, how does the size of an index file compare to the size of the original data file?
An index stores compact metadata (keys + pointers), not whole tuples. Because records usually contain many non-key attributes, the data file is much larger than the index file. Even dense indexes are typically far smaller than base data. Correct answer: the index file is significantly smaller.
Section 02
Match index type to characteristic to Binary Search on Data File
01
Match index type to characteristic
A dense index has an entry for every search-key value (often effectively every record position for that key). A sparse index intentionally skips many key values and keeps only periodic entries. That is why 'every value' maps to dense and 'only some values' maps to sparse.
02
Sparse Indices: True or False
1) True: sparse indexing assumes data is ordered by the same search key. 2) False: sparse indexes use fewer entries, so they usually consume less space than dense indexes. 3) True: each sparse entry usually points to the first record (or first key) in a block. 4) False: you first find the right sparse entry, then read and scan the target block, so it is not always exactly one access.
Guided checkpoint
State whether each statement is True or False.
03
Binary Search on Data File
Binary search on a sorted file operates over blocks, so worst-case block I/O is where is block count. Here , so , and we round up to 14. Therefore the worst case is 14 block accesses.
Guided checkpoint
A data file contains 1,000,000 records stored in 10,000 blocks. If the file is sorted and we binary search directly on blocks, how many block accesses are needed in the worst case?
Section 03
Sparse Index Performance to Why are multi-level indices used?
01
Sparse Index Performance
You first binary-search the sparse index itself: with 100 index blocks, that is about block reads. Then you follow the chosen entry to the data block, adding one more read. Total worst-case I/O is 8 accesses.
Guided checkpoint
Using the same file (10,000 blocks), we build a sparse index with one entry per block. The index fits into 100 blocks. How many block accesses are needed if we binary search index first?
02
What is the primary advantage of a dense index over a sparse index for a non-sorted search key?
Sparse indexes depend on physical ordering of the data file by the search key. If the file is not sorted on that key, sparse entries cannot safely represent skipped ranges, so lookups can miss records. A dense index is required because it has direct coverage for each searchable key/record location.
03
Why are multi-level indices used?
As an index grows, a single-level structure may no longer be cheap to search or cache. Multi-level indexing adds an index on top of the index, reducing I/O depth and improving lookup cost. This is exactly an 'index of the index,' and it helps when the lower-level index is too large for memory.
Guided checkpoint
Select all that apply.
Section 04
Multi-level Index Calculation to Primary vs. Secondary
01
Multi-level Index Calculation
A sparse level above an index usually has one entry per lower-level block. With 10,000 first-level blocks, the second level needs 10,000 entries. At 100 entries per block, that requires second-level blocks.
Guided checkpoint
A primary index has 10,000 blocks. We create a second-level sparse index on top. Each index block holds 100 entries. How many blocks does second-level index occupy?
02
A 'Primary Index' is defined as an index where...
A primary (clustered) index is defined by physical file order, not by key uniqueness. The indexed attribute is the one that determines sequential storage order of records on disk. So it is not 'must be primary key' and not 'always dense.'
03
Primary vs. Secondary
If the table is physically sorted by the indexed attribute, that index is primary/clustered. If the table is not physically sorted by that attribute, the index is secondary/non-clustered. So sorted attribute -> primary, unsorted attribute -> secondary.
Section 05
Can a secondary index (on an unsorted file) be sparse? to What is the benefit of using a bucket (indirection) level in a secondary index?
01
Can a secondary index (on an unsorted file) be sparse?
On unsorted data, there is no stable block-range ordering by the search key, so sparse skipping is invalid. A secondary index therefore needs dense coverage so every relevant key occurrence can be reached. Correct answer: no, it must be dense.
02
If we build a secondary index on a non-unique attribute (e.g., State), how can duplicates be handled?
For non-unique keys, an index can either store repeated key entries (one pointer per matching record) or store one key entry that points to a bucket/list of record pointers. Both are standard designs. It is not impossible, and sparse indexing does not solve duplicate-pointer requirements on unsorted secondary access.
Guided checkpoint
Select all that apply.
03
What is the benefit of using a bucket (indirection) level in a secondary index?
A bucket (indirection) layer lets the main index keep one entry per distinct key while the bucket stores potentially many record pointers. This reduces main-index bloat and cleanly handles duplicates. It mainly improves structure and space efficiency of index organization, not sparsity guarantees.
Section 06
Clustered vs. Non-clustered: True or False to Index operations
01
Clustered vs. Non-clustered: True or False
1) True: clustered index order matches physical data order. 2) False: a table has only one physical order, so only one clustered index. 3) True: non-clustered indexes are secondary because they do not define storage order. 4) True: range scans are usually faster on clustered data due to locality.
Guided checkpoint
State whether each statement is True or False.
02
What does ISAM stand for?
ISAM expands to Index Sequential Access Method. The name reflects a structure that supports indexed lookups while preserving sequential organization characteristics.
03
Index operations
Search means navigating the index to get a pointer and then reading the target data block (C). Insert means finding the target block and using free space or overflow handling when full (B). Delete means locating and removing the record, often with tombstone-style handling to preserve structure (A).
Section 07
In data manipulation, what is a tombstone? to Total Accesses (Multilevel)
01
In data manipulation, what is a tombstone?
A tombstone is a logical delete marker left in place of a removed record. It preserves pointer/index consistency and avoids immediate expensive reorganization. So it is not a backup and not a page type by itself.
02
When inserting into a sorted file and target block is full, which strategies can be used?
When a sorted target block is full, DBMSs can shift records to nearby blocks, use overflow pages, or allocate a new page in sequence. All three preserve sorted semantics with different performance trade-offs. Random deletion is not a valid insertion strategy.
Guided checkpoint
Select all that apply.
03
Total Accesses (Multilevel)
Because the root is already in memory, no disk I/O is needed for it. You must read one intermediate node, one leaf node, and then the actual data block. That totals 3 disk I/Os.
Guided checkpoint
Given a 3-level index (Root -> Intermediate -> Leaf) and data file: root is in memory; intermediate and leaf levels are on disk; data file is on disk. How many disk I/Os are needed to retrieve one record?
Section 08
To search for value in a sparse index, you look for... to If an index is built on a candidate key but the file is NOT sorted by that attribute, is it primary or secondary?
01
To search for value in a sparse index, you look for...
In sparse indexing, entries represent lower bounds for ranges of data blocks. To find key , you choose the last index key not greater than (largest ), then scan forward in the pointed block/range. Looking for exact alone can fail if has no explicit sparse entry.
02
What are the costs associated with having many indices on one table?
Each additional index consumes storage and must be maintained whenever rows change. INSERT/UPDATE/DELETE operations become slower because multiple index structures must be updated. DBMS planning and maintenance overhead also increases. SELECTs are not universally slower; many become faster due to better access paths.
Guided checkpoint
Select all that apply.
03
If an index is built on a candidate key but the file is NOT sorted by that attribute, is it primary or secondary?
Primary vs secondary depends on physical file order, not on whether the attribute is a candidate key. If the file is not sorted by that attribute, the index is secondary (non-clustered), even if the attribute is unique.
Section 09
Index Pointers: True or False to If search key is not a candidate key (duplicates allowed) and file is sorted, sparse index entry for value points to...
01
Index Pointers: True or False
1) True: dense indexing has an entry for each search-key value occurrence (or equivalent direct coverage). 2) True: sparse entries usually reference blocks because they represent ranges. 3) True: secondary indexes on duplicates commonly use bucket/list indirection. 4) False: pointers can target any physical location; disk-surface uniformity is irrelevant.
02
Space Overhead
Each block holds index entries. For 1,000,000 records in a dense index, you need 1,000,000 entries. Required blocks are .
Guided checkpoint
A data file has 1,000,000 records. A dense index is created. Each index entry (key + pointer) is 16 bytes. Block size is 4,096 bytes. How many index blocks are required?
03
If search key is not a candidate key (duplicates allowed) and file is sorted, sparse index entry for value points to...
With duplicates in a sorted file, a sparse entry for value should lead to where starts, not to every duplicate individually. From the first occurrence block, scanning continues to retrieve all matching records. So the correct pointer target is the first block containing the first .
Section 10
In a dense index on a non-sorted file, how are range queries (e.g., ) handled efficiently? to A 'Clustering Index' is another name for...
01
In a dense index on a non-sorted file, how are range queries (e.g., ) handled efficiently?
Even if the data file is unsorted, a dense index can be sorted by key. Range queries then locate the lower bound in index order and scan adjacent index entries until the upper bound, following pointers to records. This avoids full table scans for range predicates.
02
Matching performance rank (1 = Best)
For large sorted files, multi-level sparse indexing usually has the fewest I/Os (best rank). Single-level dense indexing is typically next best, since index search is efficient but structure is larger. Binary search directly on data blocks is usually slower than index-based methods, so it ranks last here.
Guided checkpoint
Rank search performance for a large sorted file (1 = Best).
03
A 'Clustering Index' is another name for...
A clustering index is a primary/clustered index where the ordering field may be non-unique (non-key). Records are physically grouped by that attribute, and index entries typically reference groups/blocks. So it is not just any secondary index or hash index.
Knowledge check
Turn understanding into recall.
The quiz now follows the same concepts in scored form. You can return to this lesson from the quiz whenever a gap appears.