Dynamic Hashing

Dynamic Hashing

AU: May-04,07,18, Dec.-08,17, Marks 13

• The problem with static hashing is that it does not expand or shrink dynamically as the size of the database grows or shrinks.

• Dynamic hashing provides a mechanism in which data buckets are added and removed dynamically and on-demand.

• The most commonly used technique of dynamic hashing is extendible hashing.

Extendible Hashing

The extendible hashing is a dynamic hashing technique in which, if the bucket is overflow, then the number of buckets are doubled and data entries in buckets are re- distributed.

Example of extendible hashing:

In extendible hashing technique the directory of pointers to bucket is used. Refer following Fig. 4.12.1

To locate a data entry, we apply a hash function to search the data we us last two digits of binary representation of number. For instance binary representation of 32* = 10000000. The last two bits are 00. Hence we store 32* accordingly.

Insertion operation :

• Suppose we want to insert 20* (binary 10100). But with 00, the bucket A is full. So we must split the bucket by allocating new bucket and redistributing the contents, bellsp across the old bucket and its split image.

• For splitting, we consider last three bits of h(r).

• The redistribution while insertion of 20* is as shown in following Fig. 4.12.2.

The split image of bucket A i.e. A2 and old bucket A are based on last two bits i.e. 00. Here we need two data pages, to adjacent additional data record. Therefore here it is necessary to double the directory using three bits instead of two bits. Hence,

• There will be binary versions for buckets A and A2 as 000 and 100.

• In extendible hashing, last bits d is called global depth for directory and d is called local depth for data pages or buckets. After insetion of 20*, the global depth becomes 3 as we consider last three bits and local depth of A and A2 buckets become 3 as we are considering last three bits for placing the data records. Refer Fig. 4.12.3.

(Note: Student should refer binary values given in Fig. 4.12.2, for understanding insertion operation)

• Suppose if we want to insert 11*, it belongs to bucket B, which is already full. Hence let us split bucket B into old bucket B and split image of B as B2.

• The local depth of B and B2 now becomes 3.

• Now for bucket B, we get and 1=001

11   100011

• For bucket B2, we get

5=101

29 = 11101

and 21 =10101

After insertion of 11* we get the scenario as follows,

Example 4.12.1 The following key values are organized in an extendible hashing technique.

13589 12 17 28. Show the extendible hash structure for this file if the hash function is h(x) =

x mod 8 and buckets can hold three records. Show how extendable hash structure changes as the result of each of the following steps:

Insert 2

Insert 24

Delete 5

Delete 12

Solution:

Step 1: Initially we assume the hash function based on last two bits, of result of hash function.

1 mod 8=1=001

3 mod 8=3 = 011

5 mod 8=5= 101

8 mod 8=0=000

9 mod 8=1=001

12 mod 8 = 4=100

17 mod 8=1=001

28 mod 84 = 100

The extendible hash table will be,

Hence we will extend the table by assuming the bit size as 3. The above indicated bucket A will split based on 001 and 101.

a) Insert 2 will be 2 mod 8 = 2 = 010. If we consider last two digits i.e. 10 then there is no bucket. So we get,

b) Insert 24 : 24 mod 8 = 0 = 000. The bucket in which 24 can be inserted is 8, 12, 28. But as this bucket is full we split it in two buckets based on digits 000 100.

c) Delete 5: On deleting 5, we get one bucket pointed by 101 as empty. This will also result in reducing the local depth of the bucket pointed by 001. Hence we get,

d) Delete 12: We will simply delete 12 from the corresponding bucket there can not be any merging of buckets on deletion. The result of deletion is as given below

Difference between Static and Dynamic Hashing

Review Questions

1. What is hashing? Explain static hashing and dynamic hashing with an example.."AU: May-18, Marks 13

2. Explain the distinction between static and dynamic hashing. Discuss the relative merits of each ris technique in database applications.  AU: Dec.-17, Marks 13

3. Describe briefly static and dynamic hashing. AU: May-04, Marks 8, Dec.-08, Marks 8