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
Dynamic Hashing
Last Updated : 21 May, 2026
Static hashing suffers when data size changes unpredictably:
Unit 5178 words13 headingsExamples included
Why Dynamic Hashing?
Static hashing suffers when data size changes unpredictably:
- Too few buckets → overflow chains → slow
- Too many buckets → wasted space
Dynamic hashing allows the hash table to grow and shrink as data changes, maintaining good performance without a fixed bucket count.
Two main forms:
- Extendible Hashing — directory-based, doubles directory on overflow
- Linear Hashing — directory-free, adds one bucket at a time
Extendible Hashing
Concept
Uses a directory (array of pointers to buckets) that can double in size. The key idea is using the first i bits of the hash value to index into the directory.
Global depth (i): number of bits used to index directory
Local depth (j): number of bits used by a specific bucket
(j ≤ i always)
Directory size = 2^i
Structure
| Directory | Buckets: |
| │ 00 │ ─────────┼──────► Bucket A (local depth 2) | [10][14] |
| │ 01 │ ─────────┼──────► Bucket B (local depth 1) | [5][9][13] |
| │ 10 │ ─────────┼──────► Bucket C (local depth 2) | [2][6] |
| └────────────────┘ └──► Bucket D (local depth 2) | [3][7] |
Search in Extendible Hashing
| Example | Global depth = 2, K=6, h(6) = ...10... |
| First 2 bits = "10" | index 2 → Bucket C |
| Search Bucket C for K=6 | Found! |
| Cost | 1 directory read + 1 bucket read |
Insert with Bucket Split
| Case 1 | Local depth j < Global depth i |
| Case 2 | Local depth j = Global depth i |
| Example | Insert into full Bucket A (local depth 2 = global depth 2) |
| Step 1: Double directory: global depth 2 | 3 (4 entries → 8 entries) |
| Step 2 | Split Bucket A into A and A' |
| Step 3 | Redistribute records using 3-bit prefix |
Extendible Hashing Diagram (After Split)
| BEFORE (Global depth 2) | AFTER INSERT (Global depth 3): |
| Dir | Bucket: Dir (8 entries): Bucket: |
| Insert 15 into B (full) | 101 ─► B' [15] |
Linear Hashing
Concept
Linear hashing adds one bucket at a time in a predetermined linear order, without using a directory. It uses a sequence of hash functions.
At any time, two hash functions are active:
h_i(K) = K mod (2^i × N) (current level)
h_{i+1}(K) = K mod (2^{i+1} × N) (next level)
Where N = initial number of buckets
Splitting proceeds through buckets in order: 0, 1, 2, ..., n−1
tracked by a split pointer (sp)
Linear Hashing Lookup
Lookup key K:
1. Compute bucket = h_i(K)
2. If bucket < split pointer (sp):
→ Bucket has been split; use h_{i+1}(K) instead
3. Access the computed bucket
This ensures records are always found correctly
even while splits are happening.
When to Split
A split is triggered when the load factor exceeds a threshold (e.g., 0.8):
After each split:
- Split pointer (sp) advances by 1
- When sp reaches the end → start new round (increment level i)
- Load factor naturally stays in acceptable range
Extendible vs. Linear Hashing
| Feature | Extendible Hash | Linear Hash |
|---|---|---|
| Directory | Yes (doubles) | No (dir-free) |
| Split trigger | Bucket overflow | Load factor |
| Buckets added | One at a time | One at a time |
| Directory overhead | Can double | None |
| Implementation | Moderate | Slightly complex |
| Search cost | 1 dir + 1 bucket | O(1) — 1 bucket |
Dynamic Hashing vs. Static Hashing
Static: Fixed B, fast for stable data, poor for growth
Dynamic: Grows gracefully, maintains O(1) search
at the cost of split overhead
Most modern in-memory hash tables use dynamic hashing.
Disk-based DBMS often prefer B+ trees over hashing
because B+ trees support both equality AND range queries.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Dynamic Hashing.
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, dynamic, hashing, dynamic hashing
Related DBMS Topics
Continue learning this concept
Unit 5Hashing TechniquesHashing is a technique for direct address computation — a hash function maps a key value directly to a bucket address disk block where the record is stored. It avoids theUnit 5Static HashingStatic hashing uses a fixed number of buckets B. The hash function always maps keys to the same set of B buckets. The number of buckets is chosen at design time and does 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 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 desUnit 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 compare alternativ