2Chapter11Indexing and Hashingb.c.11.4Answer:•With structure11.3.a:Insert9:10:InsertExercises3Delete23:Delete19:•With structure11.3.b:Insert9:Insert4Chapter 11Indexing and HashingDelete23:Delete 19:•With structure 11.3.c:Insert9:Insert10:Insert8:Delete 23:Delete 19:Exercises511.5Answer:If there are K search-key values and m −1siblings are involvedin the redistribution,the expected height of the tree is:log ⌊(m −1)n /m ⌋(K )11.6Answer:Extendable hash structure000 001010 011 100101 110 11111.7Answer:a.Delete 11:From the answer to Exercise 11.6,change the third bucketto:At this stage,it is possible to coalesce the second and third buckets.Then it is enough if the bucket address table has just four entriesinstead of eight.For the purpose of this answer,we do not do the coalescing.b.Delete 31:From the answer to 11.6,change the last bucket to:6Chapter11Indexing and Hashingc.Insert1:From the answer to11.6,change thefirst bucket to:d.Insert15:From the answer to11.6,change the last bucket to:11.8Answer:The pseudocode is shown in Figure11.1.11.9Answer:Let i denote the number of bits of the hash value used in thehash table.Let bsize denote the maximum capacity of each bucket.Thepseudocode is shown in Figure11.2.Note that we can only merge two buckets at a time.The common hashprefix of the resultant bucket will have length one less than the two bucketsmerged.Hence we look at the buddy bucket of bucket j differing from itonly at the last bit.If the common hash prefix of this bucket is not i j,thenthis implies that the buddy bucket has been further split and merge is notpossible.When merge is successful,further merging may be possible,which is handled by a recursive call to coalesce at the end of the function.11.10Answer:If the hash table is currently using i bits of the hash value,thenmaintain a count of buckets for which the length of common hash prefixis exactly i.Consider a bucket j with length of common hash prefix i j.If the bucketis being split,and i j is equal to i,then reset the count to1.If the bucketis being split and i j is one less that i,then increase the count by1.It thebucket if being coalesced,and i j is equal to i then decrease the count by1.If the count becomes0,then the bucket address table can be reduced insize at that point.However,note that if the bucket address table is not reduced at that point,then the count has no significance afterwards.If we want to postpone thereduction,we have to keep an array of counts,i.e.a count for each value ofExercises7 functionfindIterator(value V){/*Returns an iterator for the search on the value V*/Iterator iter();Set iter.v alue=V;Set C=root nodewhile(C is not a leaf node)beginLet i=samllest number such that V<=C.K iif there is no such number i then beginLet P m=last non-null pointer in the nodeSet C=C.P m;endelse Set C=C.P i;end/*C is a leaf node*/Let i be the least value such that K i=Vif there is such a value i then beginSet iter.index=i;Set iter.page=C;Set iter.acti v e=T RUE;endelse if(V is the greater than the largest value in the leaf)then beginif(C.P n.K1=V)then beginSet iter.page=C.P n;Set iter.index=1;Set iter.acti v e=T RUE;endelse Set iter.acti v e=F AL SE;endelse Set iter.acti v e=F AL SE;return(iter)}Class Iterator{variables:value V/*The value on which the index is searched*/boolean active/*Stores the current state of the iterator(TRUE or FALSE)*/int index/*Index of the next matching entry(if active is TRUE)*/PageID page/*Page Number of the next matching entry(if active is TRUE)*/ function next(){if(active)then beginSet ret Page=page;Set retI ndex=index;if(index+1=page.size)then beginpage=page.P nindex=0endelse index=index+1;if(page.K index=V)then acti v e=F AL SE;return(ret Page,retI ndex)endelse return null;}}Figure11.1Pseudocode forfindIterator and the Iterator class8Chapter11Indexing and Hashingdelete(value K l)beginj=first i high-order bits of h(K l);delete value K l from bucket j;coalesce(bucket j);endcoalesce(bucket j)begini j=bits used in bucket j;k=any bucket withfirst(i j−1)bits same as thatof bucket j while the bit i j is reversed;i k=bits used in bucket k;if(i j=i k)return;/*buckets cannot be merged*/if(entries in j+entries in k>bsize)return;/*buckets cannot be merged*/move entries of bucket k into bucket j;decrease the value of i j by1;make all the bucket-address-table entries,which pointed to bucket k,point to j;coalesce(bucket j);endFigure11.2Pseudocode for deletioncommon hash prefix.The array has to be updated in a similar fashion.Thebucket address table can be reduced if the i th entry of the array is0,wherei is the number of bits the table is using.Since bucket table reduction isan expensive operation,it is not always advisable to reduce the table.Itshould be reduced only when sufficient number of entries at the end ofcount array become0.11.11Answer:We reproduce the instructor relation below.Exercises9 ID dept salary10101Comp.Sci.Wu9000015151MusicEinstein9500032343HistoryGold8700045565Comp.Sci.Califieri6200076543FinanceCrick7200083821Comp.Sci.Kim80000a.Bitmap for salary,with S1,S2,S3and S4representing the given inter-vals in the same orderS1000000000000S3010*********b.The question is a bit trivial if there is no bitmap on the deptname attribute is:Comp.Sci010********* Music000101000000 History000000000100 Elec.Eng.010********* Finance010*********10Chapter11Indexing and HashingScan on these records with salary80000or more gives Wu and Singhas the instructors who satisfy the given query.11.12Answer:If the index entries are inserted in ascending order,the newentries get directed to the last leaf node.When this leaf node getsfilled,it is split into two.Of the two nodes generated by the split,the left nodeis left untouched and the insertions takes place on the right node.Thismakes the occupancy of the leaf nodes to about50percent,except the lastleaf.If keys that are inserted are sorted in descending order,the above situationwould still occur,but symmetrically,with the right node of a split nevergetting touched again,and occupancy would again be50percent for allnodes other than thefirst leaf.11.13Answer:a.The cost to locate the page number of the required leaf page foran insertion is negligible since the non-leaf nodes are in memory.On the leaf level it takes one random disk access to read and onerandom disk access to update it along with the cost to write onepage.Insertions which lead to splitting of leaf nodes require anadditional page write.Hence to build a B+-tree with n r entries ittakes a maximum of2∗n r random disk accesses and n r+2∗(n r/f)page writes.The second part of the cost comes from the fact that inthe worst case each leaf is halffilled,so the number of splits thatoccur is twice n r/f.The above formula ignores the cost of writing non-leaf nodes,sincewe assume they are in memory,but in reality they would also bewritten eventually.This cost is closely approximated by2∗(n r/f)/f,which is the number of internal nodes just above the leaf;we canadd further terms to account for higher levels of nodes,but these aremuch smaller than the number of leaves and can be ignored.b.Substituting the values in the above formula and neglecting the costfor page writes,it takes about10,000,000∗20milliseconds,or56hours,since each insertion costs20milliseconds.Exercises11c.function insert leaf(value K,pointer P)if(tree is empty)create an empty leaf node L,which is also the rootelse Find the last leaf node in the leaf nodes chain Lif(L has less than n−1key values)then insert(K,P)at thefirst available location in Lelse beginCreate leaf node L1Set L.P n=L1;Set K1=last value from page Linsert parent(1,L,K1,L1)insert(K,P)at thefirst location in L1endfunction insert parent(level l,pointer P,value K,pointer P1)if(level l is empty)then beginCreate an empty non-leaf node N,which is also the rootinsert(P,K,P1)at the starting of the node Nreturnelse beginFind the right most node N at level lif(N has less than n pointers)then insert(K,P1)at thefirst available location in Nelse beginCreate a new non-leaf page N1insert(P1)at the starting of the node Ninsert parent(l+1,pointer N,value K,pointer N1)endendThe insert leaf function is called for each of the value,pointerpairs in ascending order.Similar function can also be build for de-scending order.The search for the last leaf or non-leaf node at anylevel can be avoided by storing the current last page details in anarray.The last node in each level might be less than halffilled.To makethis index structure meet the requirements of a B+-tree,we can re-distribute the keys of the last two pages at each level.Since the lastbut one node is always full,redistribution makes sure that both ofthen are at least halffilled.11.14Answer:In a B+-tree index orfile organization,leaf nodes that areadjacent to each other in the tree may be located at different places ondisk.When afile organization is newly created on a set of records,it ispossible to allocate blocks that are mostly contiguous on disk to leafsnodes that are contiguous in the tree.As insertions and deletions occur12Chapter11Indexing and Hashingon the tree,sequentiality is increasingly lost,and sequential access has towait for disk seeks increasingly often.a.One way to solve this problem is to rebuild the index to restoresequentiality.b.i.In the worst case each n-block unit and each node of the B+-treeis halffilled.This gives the worst case occupancy as25percent.ii.No.While splitting the n-block unit thefirst n/2leaf pages areplaced in one n-block unit,and the remaining in the second n-block unit.That is,every n-block split maintains the order.Hence,the nodes in the n-block units are consecutive.iii.In the regular B+-tree construction,the leaf pages might not besequential and hence in the worst case,it takes one seek per leafing the block at a time method,for each n-node block,we will have at least n/2leaf nodes in it.Each n-node block canbe read using one seek.Hence the worst case seeks comes downby a factor of n/2.iv.Allowing redistribution among the nodes of the same block,doesnot require additional seeks,where as,in regular B+-tree werequire as many seeks as the number of leaf pages involvedin the redistribution.This makes redistribution for leaf blocksefficient with this scheme.Also the worst case occupancy comesback to nearly50percent.(Splitting of leaf nodes is preferredwhen the participating leaf nodes are nearly full.Hence nearly50percent instead of exact50percent)。