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

ID: 3824332 • Letter: 1

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?

1Ans. Calculation::

The avg fan-out for the internal_nodes is 'fo' = ceiling(0.69*p)

= ceiling(0.69*53)

= ceiling(36.5)

= 37

number of second-level tree blocks b_2 = ceiling(b_1 / fo)

= ceiling(27,778/37)

= 751 blocks.

no. of third-level tree blocks 'b_3' = ceiling(b_2 /fo)

= ceiling(751/37)

= 20

no. of fourth-level tree blocks b_4 = ceiling(b 3 /fo)

= ceiling(20/37)

= 1

As the 4th level has only 1-block, the tree has x = 4 internl nnodes

2Ans) The no. of index_blocks is 'bi' = ( ri/bfri ) ( ri = no. of blocks data_file = 50,000.)

Therefore 'bi' = ( ri/bfri )

= 50,000/53

= 944 blocks

3Ans) 'The linear_search = 'bi/2'

= 944/2

= 472 blocks

4Ans) A binary_search "(log2_bi)" = (log_2 944)

= 10 block_accessess

5Ans) The "fan--out" 'fo' value of multi-level_index has same_value of 'blocking-factor' of 'indx_bfri' = fo

= 53 //

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