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

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

---

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.

 

---

Does the answer changes if B-Tree is used?

---

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.