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

Which of the following is correct?

  1. B-trees are for storing data on disk and B$^+$ trees are for main memory.

  2. Range queries are faster on B$^+$ trees.

  3. B-trees are for primary indexes and B$^+$ trees are for secondary indexes.

  4. The height of a B$^+$ tree is independent of the number of records.

asked in Databases by Veteran (59.9k points) | 2.4k views
how option d is incorrect ? i think it also true

2 Answers

+31 votes
Best answer
  1. False. Both r stored in disk
  2. True. By searching leaf level linearly in $B^+$ tree, we can say a node is present or not in $B^+$ tree. But for $B$ tree we have to traverse the whole tree
  3. False. $B$ tree and $B^+$ tree uses dynamic multilevel indexes
  4. False. Height depends on number of record and also max no of keys in each node (order of tree)
answered by Veteran (109k points)
edited by
on page 21 of the pdf at the link specified, it says "A B+-tree can have less levels (or higher capacity of search values) than the corresponding B-tree". Is it true? Havent read that earlier. Also cant understand how it can be reasoned.
In B tree there are only data pointer. So, every time it searched , it have to search from root

But in B+ tree there are data pointer and record pointer. So, once it comes in leaf , it can only goes to search leaf level only. It is useful because in B+ tree all nodes are present in leaves only.
> In B tree there are only data pointer. So, every time it searched , it have to search from root. But in B+ tree there are data pointer and record pointer.

Not getting whats the difference between data pointer and record pointer. Also in both all searches should start from root right? Or is it like we can start search from arbitrary interior node in B+ tree?

Also it does not explain how B+ tree height tends to be less than the corresponding B tree.

@  srestha 

as A is false, so which data structure is used for main memory ?

Binary trees , link list , queue , array...
@srestha B tree tree ptr+ Record ptr+ key value

b+ tree only at last level + record pointer; internal nodes only tree pointer and key values?
@ Rupendra can you tell me why b/b+ tree preferred for disk and binary tree,linked list etc for main memory?
BST are used for "searching" in RAM and Btrees are used for "searching" in HDD.

@Gate Fever What is the logic behind this statement?
+8 votes

The leaves (the bottom-most index blocks) of the B+ tree are often linked to one another in a linked list; this makes range queries or an (ordered) iteration through the blocks simpler and more efficient (though the aforementioned upper bound can be achieved even without this addition). This does not substantially increase space consumption or maintenance on the tree. This illustrates one of the significant advantages of a B+tree over a B-tree; in a B-tree, since not all keys are present in the leaves, such an ordered linked list cannot be constructed.
   read @ implementation

answered by Loyal (6k points)
reshown by

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
48,721 questions
52,825 answers
68,573 users