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 (59.4k points) | 1.8k 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 Boss (34.1k 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 Loyal (7.9k points)
–1 vote
Option d.
answered by Active (3.3k points)
–1 vote
Yes, ans is (D).
answered by Junior (835 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

35,487 questions
42,746 answers
42,138 users