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 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! |
Continue the lesson path
Study next in this module
01Unit 5Query ProcessingQuery processing is the set of activities involved in retrieving data from a database in response to a SQL query. It translates a high-level SQL statement...02Unit 5Static HashingStatic hashing uses a fixed number of buckets that is determined at design time and never changes. A hash function maps each search key value to one of...03Unit 5Query Optimization — Database Management SystemsQuery optimization is the process of selecting the most efficient execution plan from among all possible plans for a given SQL query. The optimizer\04Unit 5Unit 5 Summary — Storage & IndexingThis unit covered how databases physically store data and retrieve it efficiently. The fundamental trade-off throughout this unit is between storage...