ISRO2018-49

Question

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$

Comments

3 is not correct answer , we have find maximum number of node access , so for each level we access one node

why 3 is not correct

by property of B tree if tree has order 'N ' then  it can have ceil(N/2) to N child.

for maximum number of node access we take minimum child it have that is ceil(N/2).

rest calculation is same as VS answer.

---

https://gateoverflow.in/333177/gate-2020-cse-question-54

Answer 1

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=10⁶/50 = 2 * 10⁴

#Nodes in Second last level= 2*10⁴/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)

Comments

Maximum no. of nodes = Minimum no. of nodes+1

---

if it was order of leaf node then we will take 100 but if nothing is given we have to take general order that is order of intermediate node number of pointer in node will 99

---

Why can't we take

Log base100(10^6)=height of tree.

We get height 3,and level 4.

Just like complete binary tree

H=logbase2(total node).

Answer 2

ANSWER: B

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

Answer 3

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

Comments

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