The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+25 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 (69k points) | 1.6k views
why option c is false.

4 Answers

+23 votes
Best answer
Answer: D

A: Cannot compare both the trees solely on basis of this.
B: Both trees are BST.
C: False. High fanout in B+ ensures that it takes more memory than BST.
D: True. Records are stored in disk blocks.
answered by Veteran (36.4k points)
selected 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.
+12 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 (7.4k points)
–1 vote
Option d.
answered by Loyal (3.3k points)
–1 vote
Yes, ans is (D).
answered by Junior (983 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

33,593 questions
40,128 answers
38,389 users