DBMS Topics
HubUnit 1 — Introduction to DBMS & Entity-Relationship ModelAdvantages and Disadvantages of DBMSAggregationCharacteristics of DBMSData IndependenceData ModelsDatabase Users and AdministratorsDBMS LanguagesER DiagramsEntity-Relationship ER ModelIntroduction to DBMSKeys in DBMSRelationships and CardinalitySchema and InstanceSpecialization and GeneralizationUnit 1 Summary — Introduction to DBMS & ER ModelThree-Level Architecture ANSI/SPARC ArchitectureWeak Entity SetUnit 2 — Relational Model & SQLConstraints in SQLCursorsDCL and TCL CommandsDDL CommandsDML CommandsDomain Relational Calculus DRCFunctions and Stored ProceduresJoins in SQLNested Queries SubqueriesRelational AlgebraRelational CalculusRelational ModelSQL IntroductionUnit 2 Summary — Relational Model & SQLTriggers in SQLTuple Relational Calculus TRCViews in SQLArmstrong's Axioms & Closure of AttributesBoyce-Codd Normal Form BCNFClosure of AttributesDependency PreservationFifth Normal Form 5NFFirst Normal Form 1NFFourth Normal Form 4NFFunctional DependencyLossless DecompositionMultivalued DependencyNormal Forms — OverviewNormalization — IntroductionSecond Normal Form 2NFUnit 3 Summary — NormalizationThird Normal Form 3NFUnit 4 — Transaction Management & Concurrency ControlACID PropertiesCheckpointsConcurrency Control & SerializabilityDeadlock in DBMSLock-Based Protocols & Two-Phase LockingLog-Based RecoveryRecovery SystemSerializabilityShadow PagingUnit 4 Summary — Transaction Management & Concurrency ControlTimestamp-Based ProtocolTransaction ManagementTransaction StatesTwo-Phase Locking 2PLUnit 5 — Storage & IndexingB+ TreeB-TreeCost EstimationDynamic HashingFile OrganizationHashing TechniquesIndexing — IntroductionMulti-Level IndexingQuery OptimizationQuery ProcessingSingle-Level IndexingStatic HashingUnit 5 Summary — Storage & IndexingUnit 6 — Advanced Topics in DBMSBig Data and DBMSCloud DatabaseData MiningData WarehouseDatabase SecurityDistributed DatabaseDistributed Query ProcessingDistributed DBMS Architecture, Fragmentation & ReplicationMongoDB — IntroductionNoSQL DatabaseReplication in Distributed DatabasesUnit 6 Summary — Advanced Topics in DBMSViva Voce — DBMSImportant Viva Questions — DBMSInterview Questions — DBMSViva Answers — DBMSDBMS Multiple Choice Questions MCQsDBMS Lab Programs
Multi-Level Indexing
Last Updated : 21 May, 2026
As the data file grows, the index file also grows. A very large index file makes even binary search slow:
Unit 5219 words6 headingsExamples included
Problem with Single-Level Index
As the data file grows, the index file also grows. A very large index file makes even binary search slow:
| Data file | 1,000,000 records |
| Index file | 100,000 entries (sparse, one per block) |
| Index file blocks | 1,000 |
| Binary search on index | ⌈log₂(1000)⌉ = 10 block reads |
| Index file blocks | 100,000 |
| Binary search: ⌈log₂(100,000)⌉ = 17 block reads | worse |
| Solution: Build an INDEX ON THE INDEX | Multi-Level Index |
Concept of Multi-Level Indexing
A multi-level index treats the index file itself as an ordered file and builds another (sparser) index on top of it. This can be repeated, creating a tree of index levels.
| Level 3 (Top) | ┌──────────────────────────────┐ |
| Level 2 (Middle) | ┌──────────────┴───────────────┐ |
| Level 1 (Inner) | ┌──────────────┴───────────────┐ |
| Data File | ┌──────────────┴───────────────┐ |
How Multi-Level Search Works
To find a record with key K:
1. Read the top-level (Level 3) index block
→ Find the range where K falls
→ Get pointer to Level 2 block
2. Read that Level 2 index block
→ Find the range where K falls
→ Get pointer to Level 1 block
3. Read that Level 1 index block
→ Find the entry for K
→ Get pointer to data block
4. Read the data block → find the record
Total block reads = 3 (levels) + 1 (data) = 4
vs. binary search on 1,000 index blocks = 10 reads
Number of Levels Calculation
Let:
bfr_i= blocking factor of index (entries per index block)b= number of data blocks
Then:
- Level 1 index blocks = b (one entry per data block)
- Level 2 index blocks = ⌈b / bfr_i⌉
- Level 3 index blocks = ⌈(b / bfr_i) / bfr_i⌉ = ⌈b / bfr_i²⌉
- ...
- Number of levels = ⌈log_bfr_i(b)⌉
| Level 1 | 1,000,000 blocks |
| Level 2 | 10,000 blocks |
| Level 3 | 100 blocks |
| Level 4 | 1 block (root) |
Multi-Level Index Structure Diagram
| Level 2 Block | Level 2 Block | |
|---|---|---|
| [K_a | K_b | K_c ... ] | [K_p | K_q | K_r ... ] |
Multi-Level vs. B+ Tree
A pure multi-level index has a fixed tree structure and is rigid — insertions can cause cascading reorganizations.
This limitation led to the development of B-trees and B+ trees, which are self-balancing multi-level index structures that handle insertions and deletions gracefully by allowing nodes to split and merge.
Pure Multi-Level Index → Static, hard to maintain on updates
B+ Tree → Dynamic, self-balancing, preferred in practice
All modern DBMS use B+ trees (not static multi-level indexes) as the underlying index structure because they automatically balance themselves.
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 DBMS topic.
Search Terms
dbms, database management system, database notes, sql, unit, multi, level, indexing
Related DBMS Topics
Continue learning this concept
Unit 5Single-Level IndexingA single-level index is a flat index file where each index entry contains a search key value and a pointer to the corresponding data records. The index file itself is sorUnit 5Indexing — IntroductionAn index is a data structure that improves the speed of data retrieval operations on a database table. It works like the index at the back of a book — instead of scanningUnit 5Unit 5 — Storage & IndexingThis unit covers how databases physically store and efficiently retrieve data. Understanding storage structures and indexing is essential for database performance tuning Unit 5Unit 5 Summary — Storage & IndexingUnit 5B+ TreeA B+ Tree is a variation of the B-Tree where:Unit 5B-TreeA B-Tree Balanced Tree is a self-balancing, sorted tree data structure that maintains sorted data and allows searches, insertions, and deletions in Olog n time. It is des