1.8k 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

0
why option c is false.

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.
selected
0
+1
@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
+2
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.
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.

–1 vote
Option d.
–1 vote
Yes, ans is (D).