DBMS Notes
HubUnit 1 — Introduction to DBMS & Entity-Relationship ModelAdvantages and Disadvantages of DBMSAggregation — Database Management SystemsCharacteristics of DBMSData IndependenceData ModelsDatabase Users and AdministratorsDBMS LanguagesER DiagramsEntity-Relationship (ER) ModelIntroduction to DBMSKeys in DBMSRelationships and CardinalitySchema and InstanceSpecialization and GeneralizationDBMS Unit 1 Summary - Database FundamentalsThree-Level Architecture (ANSI/SPARC Architecture)Weak Entity SetUnit 2 — Relational Model & SQLConstraints in SQLCursorsDCL and TCL CommandsDDL CommandsDML CommandsDomain Relational Calculus (DRC) - Complete TutorialFunctions and Stored ProceduresJoins in SQLNested Queries (Subqueries)Relational AlgebraRelational Calculus in Database Management SystemsRelational ModelSQL IntroductionDBMS Unit 2 Summary - SQL and Relational ModelTriggers in SQL — Database Management SystemsTuple Relational Calculus (TRC)Views in SQL — Database Management SystemsArmstrong\Boyce-Codd Normal Form (BCNF) — Database Management SystemsClosure of AttributesDependency PreservationFifth Normal Form (5NF)First Normal Form (1NF) - Database NormalizationFourth Normal Form (4NF)Functional DependencyLossless DecompositionMultivalued DependencyNormal Forms — OverviewNormalization — IntroductionSecond Normal Form (2NF) — Database Management SystemsUnit 3 Summary — NormalizationThird Normal Form (3NF) — Database Management SystemsUnit 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 (2PL)Unit 5 — Storage & IndexingB+ TreeB-TreeCost EstimationDynamic HashingFile OrganizationHashing TechniquesIndexing — IntroductionMulti-Level IndexingQuery Optimization — Database Management SystemsQuery 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 (MCQs)DBMS Lab Programs
A single-level index is a flat index file where each index entry contains a search key value and a pointer to the corresponding data record(s). The index...
What is Single-Level Indexing?
A single-level index is a flat index file where each index entry contains a search key value and a pointer to the corresponding data record(s). The index file itself is sorted by the search key, allowing binary search.
| Index File (sorted by key) | Data File: |
| │ Key │ Pointer │ │ Block 1 | [R1][R2] │ |
| ├──────────┼──────────┤ ┌──────►│ Block 2 | [R3][R4] │ |
| │ K1 │ | Block1 │─────┘ │ Block 3: [R5][R6] │ |
| │ K2 │ | Block2 │─────────────► Block 4: [R7][R8] │ |
| │ K3 │ | Block3 │ └─────────────────────┘ |
| │ K4 │ | Block4 │ |
2. Clustering Index (Cluster Index)
Built on a non-key ordering attribute — the data file is ordered on this attribute, but it is not the primary key (so multiple records can have the same value).
- One index entry per distinct value of the clustering field
- Pointer points to the first block containing that value
| D1 | → Block1 |
|---|---|
| D2 | → Block2 |
| D3 | → Block3 |
3. Secondary Index
Built on a non-ordering field — the data file is NOT physically ordered on this attribute.
- Can be dense (one entry per record) or use bucket pointers
- Often uses an extra level of indirection (bucket of pointers)
- Multiple secondary indexes allowed per table
| 55000 | → {Block2, Slot1} |
|---|---|
| 62000 | → {Block1, Slot2} |
| 71000 | → {Block2, Slot2} |
| 75000 | → {Block1, Slot1} |
| 88000 | → {Block1, Slot3} |
| 90000 | → {Block2, Slot3} |
Dense vs. Sparse Index
Dense Index
- One index entry for every record in the data file
- Can find any record directly from the index
| E101 | →Blk1,S1 | ────► | Block 1: [E101] |
|---|---|---|---|
| E102 | →Blk1,S2 | ────► | [E102] |
| E103 | →Blk1,S3 | ────► | [E103] |
| E104 | →Blk2,S1 | ► | Block 2: [E104] |
Sparse Index
- One index entry for every data block (not every record)
- Smaller index file, but requires sequential scan within a block after locating the block
| E101 | →Block1 | ────► | Block 1: [E101][E102] |
|---|---|---|---|
| E104 | →Block2 | ────► | Block 2: [E104][E105] |
Comparison Table
| Index Type | Data File Order | # Entries | Key Type | Dense? |
|---|---|---|---|---|
| Primary | Ordered on key | One per block | Unique key | Sparse |
| Clustering | Ordered on non-key | One per distinct value | Non-unique | Sparse |
| Secondary | Any order | One per record | Any attribute | Dense |
Index Search Cost
| Binary search on index | ⌈log₂(b_i)⌉ block accesses |
| Then | 1 block access to retrieve the data record. |
| Table: 1,000,000 records, 10 records/block | 100,000 data blocks |
| Primary index: 100,000 entries, 100 entries/block | 1,000 index blocks |
| Binary search | log₂(1000) ≈ 10 block reads + 1 data block = 11 total |
| vs. full table scan | 100,000 block reads! |
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Single-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, single, level, indexing, single-level indexing
Related Database Management Systems (DBMS) Topics
Continue learning this concept
Unit 5Multi-Level IndexingA 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...Unit 5Indexing — IntroductionAn index is a data structure built on one or more columns of a database table that dramatically speeds up data retrieval operations. It works exactly like...Unit 5Unit 5 — Storage & IndexingThis unit addresses one of the most critical aspects of database management — how data is physically stored on disk and how it can be retrieved efficiently. While SQL andUnit 5B+ TreeA B+ Tree is a variation of the B-Tree where: - All data records (or pointers to them) are stored only in leaf nodes - Internal nodes store only keys used...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 O(log...Unit 5Cost EstimationCost estimation is the process of predicting the execution cost of a query plan without actually running it. The query optimizer uses cost estimates to...