The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
2.1k 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.6k points) | 2.1k views
0
why option c is false.

4 Answers

+23 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 (34k 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.
+6
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.
+14 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 (14.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?
0
@newdreamz-Please don't call me sir.

No.BST would require more memory because each node of a BST will hold only one search key value and each node of a BST corresponds to a disk block when we are talking about using BST as a data structure for storing the database on disk.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 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

41,078 questions
47,675 answers
147,467 comments
62,393 users