The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+26 votes

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
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
@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?
High fanout in B+ ensures that it takes more memory than BST.

wht does it mean ?
how high fan out  in B+ ensures that it takes more memory than BST? i dont get it please someone elaborate this little more
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.
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)
and sir what is thee significance of the statement that "b+ trees requires less memory than binary search trees".  is it true or false?
@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)

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
62,393 users