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
Static Hashing
Last Updated : 21 May, 2026
Static 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 5147 words14 headingsExamples included
Definition
Static 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 not change.
h: Key → {0, 1, 2, ..., B-1} (B is fixed forever)
Structure
| │ 0 │ | Block ptr │──────► [Rec_A][Rec_H] |
| │ 1 │ | Block ptr │──────► [Rec_B] |
| │ 2 │ | Block ptr │──────► [Rec_C][Rec_I][Rec_J] → [overflow] |
| │ 3 │ | Block ptr │──────► [Rec_D] |
| │ 4 │ | Block ptr │──────► (empty) |
| │ 5 │ | Block ptr │──────► [Rec_E][Rec_K] |
| │ 6 │ | Block ptr │──────► [Rec_F] |
| │ 7 │ | Block ptr │──────► [Rec_G] |
| Bucket 2 is full | overflow chaining used |
Operations
Search (Lookup)
| 4. If not found and overflow exists | follow overflow chain |
| Best case | 1 disk read (record in primary bucket) |
| Worst case | 1 + overflow_chain_length reads |
Insert
To insert record R with key K:
1. Compute bucket = h(K)
2. Read the block at that bucket
3. If space available → write R into bucket block
4. If bucket is FULL:
→ Allocate a new overflow block
→ Link it to the primary bucket block (overflow chain)
→ Write R into the overflow block
Delete
To delete record with key K:
1. Search for K (find its bucket and block)
2. Remove the record from its block
3. If the block is now empty:
→ Remove it from the overflow chain (if it was overflow)
→ Mark primary block as having free space
Overflow Chains
When a bucket overflows, a chain of overflow blocks is linked:
Primary Bucket 3:
┌────────────────────┐ ┌──────────────────┐
│[R7][R12][R23] Next │────►│[R34][R45] Next │──► NULL
└────────────────────┘ └──────────────────┘
Primary block (full) Overflow block 1
Problem with overflow chains: Long chains degrade performance from O(1) to O(n).
Bucket Overflow Causes
- Insufficient buckets: Too few buckets for the number of records
- Skewed distribution: Many keys hash to the same bucket (uneven distribution)
- Bad hash function: Not uniform enough
Load Factor
Load factor α = n / (B × slots_per_bucket)
Where:
n = number of records stored
B = number of buckets
slots_per_bucket = how many records fit in one bucket block
Good load factor: α ≈ 0.7 to 0.8
α > 1.0 → overflow chains forming (performance degrades)
Choosing Number of Buckets
B = ⌈n / (l × α)⌉
Where:
n = expected number of records
l = number of records per bucket (blocking factor)
α = target load factor (usually 0.7–0.8)
Example:
n = 1,000,000 records
l = 20 records per bucket block
α = 0.8
B = ⌈1,000,000 / (20 × 0.8)⌉ = ⌈62,500⌉ = 62,500 buckets
Advantages and Disadvantages
Advantages
- Very fast equality search: O(1) average
- Simple to implement
- Good performance when data size is known in advance
Disadvantages
| If data grows: overflow chains | slow |
| If data shrinks: many empty buckets | wasted space |
| 4. Bad hash functions | clusters → long overflow chains |
Static Hashing Performance
| Search/Insert/Delete | 1 disk read + O(1) computation = O(1) |
| Search | 1 + (overflow chain length) disk reads |
| As load factor increases | chains grow → performance degrades |
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Static 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, static, hashing, static hashing
Related DBMS Topics
Continue learning this concept
Unit 5Dynamic HashingStatic hashing suffers when data size changes unpredictably: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 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