The Gateway to Computer Science Excellence
+1 vote

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$
in Databases by Veteran (431k points)
recategorized | 2.7k views

4 Answers

+14 votes
Best answer

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
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.


+6 votes


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 by
+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)

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

0 votes
"C" ans
by Active (2.3k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,367 answers
105,271 users