The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+27 votes
2.4k 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

asked in Databases by Veteran (59.7k points) | 2.4k views
0
why option c is false.

4 Answers

+25 votes
Best answer

Answer: D

  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.
answered by Boss (34.1k points)
edited by
0
+2
@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
+4
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.
+10
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.
0
What is fanout in B+ trees?
+1
@gupta

fanout means number of pointer coming out from the node
0

@Gurdeep Saini

Can you Explain in detail ??

0
But height will be less compared to bst
+15 votes
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.

So, answer is option (d)
answered by Boss (19.1k points)
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?
+2
@newdreamz-Please don't call me sir.

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

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

+1
@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 :)
+1

@Ayush+Upadhyaya

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

@Ayush+Upadhyaya

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

Anyone who is currently solving computer networks please answer above question. 

 

 

–1 vote
Option d.
answered by Active (3.3k points)
–1 vote
Yes, ans is (D).
answered by Junior (855 points)
Answer:

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

44,456 questions
49,912 answers
165,381 comments
65,897 users