Dynamic Hashing in Data structure| Dynamic Hashing in DBMS |Extendible Hashing in Data structure

 

Dynamic Hashing

Dynamic Hashing allows the hash table to grow or shrink dynamically according to the amount of data.

• The number of buckets changes dynamically.
• Bucket overflow is handled by splitting or expanding.
• It is suitable for storing large amounts of data.

Extendible Hashing

Extendible Hashing is a dynamic hashing technique.

• It uses a directory with Global Depth.
• Each bucket has a Local Depth.(Last bit)
• When a bucket becomes full, it is split into two buckets.
• If required, the directory size is doubled.
• It uses suffix bits (last bits) to identify the buckets.

Example

Values = 11, 18, 20, 25, 29, 33

Bucket Size = 2(Cannot store more than 2 value)

Binary Representation

Value	Binary	Last 1 Bit	Last 2 Bits	Last 3 Bits
11	1011	1	11	011
18	10010	0	10	010
20	10100	0	00	100
25	11001	1	01	001
29	11101	1	01	101
33	100001	1	01	001

Case 1: Global Depth = 1
2¹=2 (Directory Size=2)

So, last 1 bit is used.

Directory	Last 1 Bit	Bucket
A	0	18, 20
B	1	11, 25

Bucket size = 2.

Now 29 and 33 need to be inserted but the bucket becomes full 

29 and 33 has(last bit end with 1).So (directory B)splitting is required.

**(if the bucket becomes full ,the last bit end with 0 means (directory A)splitting is required.)**

Case 2: Global Depth = 2

2²=4(Directory Size=4)

Now last 2 bits are used.

Directory	Last 2 Bits	Bucket
A	00	20
B₁	01	25, 29
A	10	18
B₂	11	11

Now 33 has ( last 2 bits 01), so the bucket containing 25, 29 becomes full.

Therefore,(directory B)further splitting is required.

Case 3: Global Depth = 3

2³=8(Directory Size=8)

Now last 3 bits are used.                                    

Directory	Last 3 Bits	Bucket
A	000	—
B₁	001	25, 33
A	010	18
B₂	011	11
A	100	20
B₃	101	29
A	110	—
B₄	111	—

ALL values are inserted.Thus, the directory grows from 2 → 4 → 8 entries as more records are inserted.

Handwritten Notes- Download PDF

Video Explanation- Watch on YouTube