hashing ( ( ( ( figure extendible hashingoriginal data let us supposefor the momentthat our data consists of several -bit integers figure shows an extendible hashing scheme for these data the root of the "treecontains four pointers determined by the leading two bits of the data each leaf has up to elements it happens that in each leaf the first two bits are identicalthis is indicated by the number in parentheses to be more formald will represent the number of bits used by the rootwhich is sometimes known as the directory the number of entries in the directory is thus dl is the number of leading bits that all the elements of some leaf have in common dl will depend on the particular leafand dl < suppose that we want to insert the key this would go into the third leafbut as the third leaf is already fullthere is no room we thus split this leaf into two leaveswhich are now determined by the first three bits this requires increasing the directory size to these changes are reflected in figure notice that all the leaves not involved in the split are now pointed to by two adjacent directory entries thusalthough an entire directory is rewrittennone of the other leaves is actually accessed if the key is now insertedthen the first leaf is splitgenerating two leaves with dl since the only change required in the directory is the updating of the and pointers see figure this very simple strategy provides quick access times for insert and search operations on large databases there are few important details we have not considered firstit is possible that several directory splits will be required if the elements in leaf agree in more than leading bits for instancestarting at the original examplewith if and finally are insertedthe directory size must be increased to to distinguish between the five keys this is an easy detail to take care ofbut must not be forgotten secondthere is the possibility of duplicate keysif there are more than duplicatesthen this algorithm does not work at all in this casesome other arrangements need to be made