Express the algorithm for insertion and deletion of index entries in the extendable hashing schema using pseudocode.

Question

What will be an ideal response?

Answer 1

```
proc insert(ent)

// ent is the entry to be inserted;
// h is a hash function that that produces b bits;
// ch is the current hash level;
// D[i] is the i th entry in the directory;
// bl[i] is the level of the i th bucket

if bucket ?D[hch(ent)] is not full then store ent in that bucket;
else // D[hch(ent)] is full, call that bucket Bi
if bl [i ] < ch then
create a new bucket, Bi +2ch ?1;
D[i + 2ch?1]= &(Bi +2ch ?1); // store pointer to new bucket in directory
//rehash the elements of Bi to Bi and Bi +2ch ?1
put each element, e, of Bi in D[hch(e)];
bl [i ] and bl [i + 2ch?1] are set to bl [i]+ 1;
insert(ent); return;
else //bl[i]= ch
if ch = b then halt;
else // split directory
ch := ch + 1;
( i)(2ch?1 i < 2ch) D[i] := D[i - 2ch?1];
( i)(2ch?1 i < 2ch) bl [i ] := bl [i - 2ch?1];
insert(ent); return;
endproc
```