+1 vote
2.7k views

in a file which contains $1$ million records and the order of the tree is $100$, then what is the maximum number of nodes to be accessed if $B$+ tree index is used?

1. $5$
2. $4$
3. $3$
4. $10$

recategorized | 2.7k views

We need to find the maximum no. of nodes to be accessed so consider the minimum fill factor.

Here,order of b+tree= #ptrs per node=p=100

Mini. ptrs per node=$\left \lceil \frac{p}{2} \right \rceil$=50

#Nodes in last level=106/50 = 2 * 104

#Nodes in Second last level= 2*104/50 =400

#Nodes in Third last level= 400/50 =8

#Nodes in Forth last level= 8/50 =1

The maximum no. of nodes to be accessed = #B+ tree levels = 4 Ans(b)

by Boss (10.9k points)
selected by
0
but for root node minimum order in b+ tree can be 2 , so
2 in level 1 - root
2*49 in level 2
2*50*49 in level 3
2*50*50*49 in level 4
1000000 finally in level 5
so ans is 5 in this way
please hel[ me out with it
0

I think bottom approach is better as in top down approach the last level unnecessarily acquires excess keys. Also if last level is seen it has the capacity to keep 12250000 keys in total with 49 keys/node and due to actual file size the height of the B+ tree is definitely 4 at some paths and 3 at via other paths. Such a B+ tree with first level as this can't exist for 1 million records.

P.S Since file size(no. of records) mentioned then its wiser to go bottom up.

### B+- Trees

• If there are K search-key values in the file, the path is no longer than ⎡ log⎡n/2⎤ (K)⎤.
•  With 1 million search key values and n = 100, at most log50(1,000,000) = 4 nodes are accessed in a lookup.
•  Contrast this with a balanced binary tree with 1 million search key values — around 20 nodes are accessed in a lookup
by Active (1.5k points)
edited
+1 vote

Option C)

last level will contain 1000000/100=10000 nodes

second last level 10000/100=100 nodes

and root node 100/100=1 node

hence max number of node need to be acessed =3

by (181 points)
+1

This should be the "minimum" number of nodes that need to be accessed.

"C" ans
by Active (2.3k points)

+1 vote