1. What is the number of B-+tree internal nodes at the next higher level needed

Question

1. What is the number of B-+tree internal nodes at the next higher level needed if blocks are approximately 69% full (round up for convenience)?

2. How many index blocks bi are needed to build the single level primary index?

3. How many block accesses on the average are needed to fetch a record by doing linear search on the single level index part?

4. What is the least number of block accesses to fetch a record by using single level primary index with binary search?

5. What is the fan-out value if multi-level index is used?

Explanation / Answer

1. We can calculate the number of levels as follows:The average fan-out for the internal nodes (rounded up for convenience) isfo = ceiling(0.69*p) = ceiling(0.69*53) = ceiling(36.5) = 37number of second-level tree blocks b 2 = ceiling(b 1 /fo) = ceiling(27,778/37)= 751 blocks.number of third-level tree blocks b 3 = ceiling(b 2 /fo) = ceiling(751/37)= 20number of fourth-level tree blocks b 4 = ceiling(b 3 /fo) = ceiling(20/37) = 1Since the fourth level has only one block, the tree has x = 4 levels (counting theleaf level).

2.The number of index blocks is bi = (ri/bfri), where the ri equal to the number ofblocks in the data file, which is 50,000.So, bi = (ri/bfri) = (50,000/53)= 944 blocks.

3.The linear search = bi/2 = 944/2 = 472 blocks

4. A binary search(log2bi)=(log2944)= 10 block access.

5.The fan-out fo value of the multi-level index has the same value of the blocking factorof the index bfri = fo = 53

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.