# GATE2005-28

5.9k views

Which of the following is a key factor for preferring $B^+$-trees to binary search trees for indexing database relations?

1. Database relations have a large number of records

2. Database relations are sorted on the primary key

3. $B^+$-trees require less memory than binary search trees

4. Data transfer form disks is in blocks

1
why option c is false.

1. Cannot compare both the trees solely on basis of this.
2. Both trees are BST.
3. False. High fanout in B+ ensures that it takes more memory than BST.
4. True. Records are stored in disk blocks.

edited by
3
@Vaishali: B trees and Binary Search Trees are two different data structures

@Rajarshi: How does data transfer from disk in blocks influence the preference of B+ Tree over BST?
0
High fanout in B+ ensures that it takes more memory than BST.

wht does it mean ?
0
how high fan out  in B+ ensures that it takes more memory than BST? i dont get it please someone elaborate this little more
8
Comparing both trees by the number of nodes, we can say that a tree with higher fan-out occupies more memory due to the requirement of storing pointers to all children.
25
In case of a BST, which is usually implemented as an in-memory data structure, each key value corresponds to a single record entry. Whereas in case of B+ Tree, the transfer of data is in units of blocks and hence supports a greater locality of reference.

In case a node in BST points to a block where the record associated with the key is present, we also lack the facility of multiple search queries on the same block which is supported by B+ Tree. Hence reducing the query efficiency.
1
What is fanout in B+ trees?
3
@gupta

fanout means number of pointer coming out from the node
0

Can you Explain in detail ??

0
But height will be less compared to bst
Since, a node of b+tree can pack much more search values as compared to a node of a Binary search tree, the search operation tends to be faster as the information on disk is stored in form of blocks and each node of B+ tree and BST corresponds to a disk block being occupied.

So obviously it would be more beneficial to have more than one values to examine at a time when we pick up a disk block as compared to examining only one value at a time when we use BST where each node of it has only one key and corresponds to a disk block.

0
and sir what is thee significance of the statement that "b+ trees requires less memory than binary search trees".  is it true or false?
1

No.$B^+$ would require less memory . Your BST would have more nodes and more height than the corresponding B+ tree, because for the same node(means given same disk block), B+ tree packs multiple keys into it, but your BST packs only 1 key per node or per disk block.
1

Ayush Upadhyaya as per your explanation on c option above, why then c is not the ans??

2
@meghna-"Which of the following is a key Factor"-Makes option (d) strongest.

$B^+$ tree would take less memory than BST, but the problem is that the database is stored on Disk in form of blocks, and that doesn't need any memory. It needs disk blocks and an organisation to search for the information which requires a minimum number of disk block fetches. And it should?
Why? 1 disk block access is of the order of ms whereas 1 memory read is of the order of ns. Huge difference.
0
Okay got your point, thanks :)
2

No.B+ would require less memory

Please check if this understanding is right

It is because in terms of pointers only For storing keys anyway we require equal memory in both.

Suppose if 15 index record are there..in BST we will be having 4 levels and #nodes = 15 and hence #of disk pointers = 15*2 ..2 per node

But if we consider B+ order 4 then we can pack 15 keys in 5 nodes and 4 block pointers per node which is less than BST

That's why B+ will take less space than BST

0
@jatin-yes now you see why B+ tree would take less disk blocks than a bst.And yes, I had given the same reasoning that why B+ tree would take less space than BST.
0

https://gateoverflow.in/646/gate2000-1-22-ugcnet-june2012-ii-11

1. Disk access is much slower than memory access
2. Disk data transfer rates are much less than memory data transfer rates

Why 2 is not reason to go for B/B+ over bsts

0

https://gateoverflow.in/258865/me-single-subject

0

In selected answer it is given B+ tress need more space than BST

0

@jatin khachane 1

So what is final ?? I mean B+ tree takes need more or less space than BST??

0
It depends on what is the value of  child pointers it contains.

If you make p=2 which means in B+ tree each node will point to  2 child nodes ( which is same as case of BST) then B+ tree will take more memory because in each internal node also it will contain a duplicate key value.
1 vote
A. Number of keys does'nt matter as B+ tree can be used to store less keys also.

B. If indexing is done on primary key, then it will take less time for B+ tree because of less no. of levels. But it is not necessary that indexing will always be done on primary key.
so not sufficient to answer question.

C. For same no. of keys, Binary tree will have more no. of pointers(block & record pointers)  in contrast to B+tree. So Binary tree will take more space.
Also in every node, only one key record pair & 2 block pointers are there, it waste most of the block space & will have more levels which will increase I/O cost.

D. Since secondary memory is organised in blocks, B+tree will a good compatable data structure as it keeps more keys in one block which strongly supports locality of reference hence reduces I/O cost.

Option C & D both are correct but D is comparatively strong.
0
Yes, because B Tree or B+ Tree both are dynamic multi level indexing data structure, and thus here major concern is for time rather than space so D is possibly the best suited option.
–1 vote
Option d.
–1 vote
Yes, ans is (D).

## Related questions

1
4.9k views
The following table has two attributes $A$ and $C$ where $A$ is the primary key and $C$ is the foreign key referencing $A$ ... $(5, 2)$ and $(7, 2)$ $(5, 2), (7, 2)$ and $(9, 5)$ $(3, 4), (4, 3)$ and $(6, 4)$
Let $E_1$ and $E_2$ be two entities in an $E/R$ diagram with simple-valued attributes. $R_1$ and $R_2$ are two relationships between $E_1$ and $E_2$, where $R_1$ is one-to-many and $R_2$ is many-to-many. $R_1$ and $R_2$ do not have any attributes of their own. What is the minimum number of tables required to represent this situation in the relational model? $2$ $3$ $4$ $5$
Let r be a relation instance with schema R = (A, B, C, D). We define $r_1 = \pi_{A, B, C} (R)$ and $r_2=\pi_{A, D} (r)$. Let $s =r_1 \: * \: r_2$ where $*$ denotes natural join. Given that the decomposition of $r$ into $r_1$ and $r_2$ is lossy, which one of the following is TRUE? $s \subset r$ $r \cup s =r$ $r \subset s$ $r*s=s$
A B-Tree used as an index for a large database table has four levels including the root node. If a new key is inserted in this index, then the maximum number of nodes that could be newly created in the process are $5$ $4$ $3$ $2$