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
Unit 5 Summary — Storage & Indexing
Last Updated : 21 May, 2026
Unit 5158 words11 headingsTables includedExamples included
Quick Reference
File Organization Comparison
| Heap | Insert O(1), Search O(N), Range: Poor |
| Sequential | Insert O(N), Search O(logN), Range: Excellent |
| Hashed | Insert O(1), Search O(1), Range: Poor |
| Clustered | Insert O(logN), Search O(logN), Range: Excellent |
Index Types
| Type | Built On | Density | Order Required |
|---|---|---|---|
| Primary | Ordering key | Sparse | Yes |
| Clustering | Non-key ordering field | Sparse | Yes |
| Secondary | Any non-ordering field | Dense | No |
Dense vs. Sparse Index
Dense: One entry per RECORD → larger index, faster exact lookup
Sparse: One entry per BLOCK → smaller index, needs intra-block scan
B-Tree vs B+ Tree
B-Tree: Data in ALL nodes (internal + leaf); no leaf linking
B+ Tree: Data ONLY in leaf nodes; leaves linked as sorted list
→ Higher fan-out → shorter tree → used in all modern DBMS
B+ Tree Operations Cost
| Search | O(log_n N) ≈ 3–4 disk reads for millions of records |
| Insert | O(log_n N) + occasional splits |
| Delete | O(log_n N) + occasional merges |
| Range | O(log_n N + k) where k = result set size |
Hashing
| Static | Fixed B buckets; fast for stable data; overflow chains |
| Extendible | Directory doubles on split; O(1) search; dir overhead |
| Linear | No directory; splits one at a time; no dir doubling |
| All hashing | O(1) equality search; POOR range queries |
Query Processing Steps
SQL → Parse → Translate to Rel. Algebra → Optimize → Execute
Join Algorithm Costs
| Algorithm | Cost |
|---|---|
| Nested Loop | b(R) + n(R) × b(S) |
| Block Nested Loop | b(R) + ⌈b(R)/(M−2)⌉ × b(S) |
| Sort-Merge | ≈ 3(b(R) + b(S)) |
| Hash Join | 3(b(R) + b(S)) |
| Index NL Join | b(R) + n(R) × (h_i + 1) |
Key Cost Estimation Formulas
| Full scan | b(R) |
| B+ tree primary | h_i + 1 |
| B+ tree secondary | h_i + n(R)/V(A,R) |
| Join result size | n(R) × n(S) / max(V(A,R), V(A,S)) |
Optimization Heuristics
- Push selections (σ) down the query tree — filter early
- Push projections (π) down — drop columns early
- Most restrictive condition first
- Use indexes on WHERE / JOIN columns
- Join smaller intermediate results first
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Unit 5 Summary — Storage & 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, summary, unit 5 summary — storage & indexing
Related DBMS Topics
Continue learning this concept
Unit 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 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 5Multi-Level IndexingAs the data file grows, the index file also grows. A very large index file makes even binary search slow: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 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