DBMS Notes
A single-level index works well when the index itself is small enough to fit in memory. However, as databases grow to millions or billions of records, even...
The Problem with Single-Level Indexes
A single-level index works well when the index itself is small enough to fit in memory. However, as databases grow to millions or billions of records, even the index file becomes too large for efficient in-memory searching. If the index spans thousands of disk blocks, searching it requires multiple disk accesses — defeating the purpose of indexing.
Consider a file with one million records. A dense index has one million entries. If each index entry is 15 bytes and a disk block holds 4096 bytes, the index occupies approximately 3,663 blocks. A binary search on this index requires log₂(3663) ≈ 12 disk accesses — still expensive when the goal is minimal I/O.
The solution is multi-level indexing — building an index on the index, creating a hierarchy where each level reduces the search space dramatically.
How Multi-Level Search Works
| Example | Find employee with ID = 5678 |
| 5678 falls between 5000 and 7000 | follow pointer to Level 2 block |
| 5678 falls between 5600 and 5800 | follow pointer to Level 1 block |
| 5678 falls between 5660 and 5680 | follow pointer to data block |
| Total disk accesses | 3 (excluding top level if cached) |
Number of Levels Required
The number of levels depends on the blocking factor of the index (how many index entries fit in one block):
Let
n = number of records in data file
bfr_i = index blocking factor (entries per index block)
Number of first-level entries = n (dense) or n/bfr_data (sparse)
Number of levels = ⌈log_{bfr_i}(first_level_entries)⌉
Example
n = 1,000,000 records
bfr_i = 200 entries per index block (typical)
First-level entries: 1,000,000
Levels needed: ⌈log₂₀₀(1,000,000)⌉ = ⌈2.6⌉ = 3 levels
Access cost: 3 block reads (one per level) + 1 data block read = 4 total
Compare: Without index, sequential scan = 10,000 block reads!
Multi-Level Index Structure
| Level 3 (Top Level) | [ K1 | K2 | K3 ] ← 1 block (fits in memory) |
| Level 2 | [Block] [Block] [Block] ← few blocks |
| Level 1 | [Blk][Blk]...[Blk][Blk]...[Blk] ← many blocks |
| Data File | [===] [===] [===] [===] [===] ← data blocks |
Each non-leaf level acts as a sparse index on the level below. The search navigates from the top level downward, reading exactly one block per level.
The Natural Evolution to B-Trees
Multi-level indexing as described above is a static structure — it works perfectly for read-only or rarely-updated data. However, insertions and deletions create problems:
B-trees and B+ trees solve these problems by making the multi-level index dynamic — they automatically rebalance during insertions and deletions through node splitting and merging. A B+ tree is essentially a multi-level index that maintains itself.
| Multi-Level Index | B+ Tree Evolution: |
| Static multi-level | Fixed structure, manual reorganization |
| B+ Tree | Self-balancing, automatic splitting/merging |
| Both have | O(log n) access time, hierarchical structure |
| B+ Tree adds | Dynamic insertion/deletion, guaranteed minimum occupancy |
Comparison: Single-Level vs. Multi-Level
| Aspect | Single-Level Index | Multi-Level Index |
|---|---|---|
| Structure | Flat file of index entries | Hierarchy of index levels |
| Search method | Binary search on index file | Top-down traversal (one block per level) |
| Search cost | O(log₂ n) block reads | O(log_{bfr} n) block reads |
| Performance | Good for small indexes | Essential for large indexes |
| Update cost | Moderate | High (static) or managed (B-tree) |
| Practical form | Rarely used alone for large files | B+ tree (dynamic multi-level) |
Practical Example with Numbers
Given
- Data file: 300,000 records
- Record size: 100 bytes
- Block size: 4096 bytes
- Key size: 10 bytes, pointer size: 6 bytes
- Index entry size: 10 + 6 = 16 bytes
Calculations
Data blocking factor: 4096/100 = 40 records per block
Data file blocks: 300,000/40 = 7,500 blocks
Index blocking factor (bfr_i): 4096/16 = 256 entries per index block
First-level entries (sparse): 7,500 (one per data block)
First-level blocks: 7,500/256 = 30 blocks
Second-level entries: 30 (one per first-level block)
Second-level blocks: 30/256 = 1 block ← fits in single block!
Total levels: 2
Search cost: 2 index reads + 1 data read = 3 block accesses
Without any index: 7,500/2 = 3,750 average block reads (linear scan)
Improvement: 3,750/3 = 1,250x faster!
Key Points to Remember
- Multi-level indexing solves the problem of indexes that are themselves too large for efficient searching
- Each level is a sparse index on the level below, dramatically reducing entries at each step
- The number of levels is logarithmic: log base (blocking factor) of (number of entries)
- Multi-level indexes are the conceptual foundation for B-trees and B+ trees
- Static multi-level indexes are impractical for dynamic data — use B+ trees instead
- The top level should ideally fit in a single disk block (cached in memory for zero-cost access)
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Multi-Level Indexing.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Database Management Systems (DBMS) topic.
Search Terms
dbms, database management systems (dbms), unit, multi, level, indexing, multi-level indexing
Related Database Management Systems (DBMS) Topics