24,865 views
53 votes
53 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

5 Answers

Best answer
45 votes
45 votes

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.
edited by
44 votes
44 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)
4 votes
4 votes
A. Number of keys does'nt matter as B+ tree can be used to store less keys also.

B. If indexing is done on primary key, then it will take less time for B+ tree because of less no. of levels. But it is not necessary that indexing will always be done on primary key.
so not sufficient to answer question.

C. For same no. of keys, Binary tree will have more no. of pointers(block & record pointers)  in contrast to B+tree. So Binary tree will take more space.
Also in every node, only one key record pair & 2 block pointers are there, it waste most of the block space & will have more levels which will increase I/O cost.

D. Since secondary memory is organised in blocks, B+tree will a good compatable data structure as it keeps more keys in one block which strongly supports locality of reference hence reduces I/O cost.

Option C & D both are correct but D is comparatively strong.
3 votes
3 votes
One thing that we have to take care of is that all these algorithms that we use like binary search trees etc work efficiently when our data is in primary (RAM) memory. But here, what we are doing is we are fetching our data from disks and the speed mismanagement of RAM and Disk is so huge (speed of RAM is in ns and that of DISK is in ms) that BST will literally be of no use fetching blocks from there. That's why we have something like B/B+ trees which help us fetching the data into our primary memory and for once as the block of data comes into the main memory we can apply any algorithm afterwards.

 

This is the basic idea of using B/B+ trees over BST for indexing databases.

 

D is the correct option.
Answer:

Related questions

39 votes
39 votes
3 answers
1
Kathleen asked Sep 22, 2014
19,956 views
The following table has two attributes $A$ and $C$ where $A$ is the primary key and $C$ is the foreign key referencing $A$ with on-delete cascade.$$\begin{array}{|c|c|} \...
66 votes
66 votes
8 answers
4
Ishrat Jahan asked Nov 3, 2014
18,467 views
A B-Tree used as an index for a large database table has four levels including the root node. If a new key is inserted in this index, then the maximum number of nodes tha...