MADE EASY TEST SERIES

Question

Which of the following statement is true for B tree and B+ tree index?

(a). B tree index is faster for range queries than B+ tree index.

(b). If disk block allocated for B+ tree index and the same size disk block is allocated for B tree index, then number of index blocks and I/O cost of B+ tree index is less than or equal to B tree index for given distinct keys.

(c). If disk block allocated for B+ tree index and the same size disk block is allocated for B tree index, then B tree index access cost is less than or equal to B+ tree for given distinct keys.

(d). If number of keys that can be stored in B tree and B+ tree index is same, then I/O cost of B+ tree index is less than or equal to I/O cost of B tree index for random access of same key from set of distinct keys.

Comments

How to solve this question?

---

is ans D)??

---

@Srestha maam, answer is B

---

a) is incorrect  because searching of B+ tree is much faster because B+ tree has 2 pointer block pointer and index pointer for searching

c) incorrect for same reason

d)false I think, keys of B and B+ tree both same means,memory space taken by B+ tree much than B tree

b) Here telling disk block means memory space of B and B+ tree are same, then B+ tree have less no of keys

---

http://users.cms.caltech.edu/~donnie/cs121/CS121Lec11.pdf

---

@srestha maam, for option (b), if memory space for both b tree and b+ tree are the same, then why will number of index blocks be less for b+ tree than that of b tree?Isnt it true that b+ tree always require more number of index blocks than corresponding b tree for some given set of keys since keys are repeated in case of b+ trees?

---

if block size is the same for both b tree and b+ tree..b tree will be able to store more number of keys than a b+ tree since keys are repeated in b+ trees but not in b trees..moreover keys and record pointers are present in the last level of b+ tree..so all the intermediate levels have to be accessed before reaching the last level and fetching the corresponding block from disk..but for B trees, since keys and record pointers are  distributed throughout the tree, so for some of the keys,we might not have to go till the leaf level to fetch the corresponding record and disk I/O cost reduces in this case..isnt it?

---

in D) it is telling disk block size is same

that means allocated space will be same

then what about IO cost?

---

answer will be option B) because index blocks of B-tree have (Record pointer ,block pointer ,search key )more pointers as compared to B+ tree (block pointer , search key) i.e,B+tree will occupy more keys in a perticular block as compared to B-tree...so B+tree will required less number of index levels as compared to B-tree ,less number of levels will cause less I/O cost...correct me if i am wrong.

---

B Trees  see this and plzz tell difference

---

Should be D.

• Because B+ trees don't have data associated with interior nodes, more keys can fit on a page of memory. Therefore, it will require fewer cache misses in order to access data that is on a leaf node.

As there will be fewer cache miss IO cost should be less. Number of index block required in B+ tree is more than B tree.

https://stackoverflow.com/questions/870218/differences-between-b-trees-and-b-trees

---

Because B trees contain data with each key, frequently accessed nodes can lie closer to the root, and therefore can be accessed more quickly.

@smsubham in option (d) the record that is accessed is the same record so access time of B tree should be faster.