GATE CSE 2000 | Question: 1.22, UGCNET-June2012-II: 11

Question

B$^{+}$-trees are preferred to binary trees in databases because

• A. Disk capacities are greater than memory capacities
• B. Disk access is much slower than memory access
• C. Disk data transfer rates are much less than memory data transfer rates
• D. Disks are more reliable than memory

Comments

Plz  explain option A???

---

@Arjun sir, why option A not correct ?

My explanation:  since disks are larger in size hence we try to minimize the number of accesses by using B/B+ trees. Therefore option A should be correct. 

---

Aren’t both the options \((B)\) and \((C)\) synonymous?

Answer 1

Answer is (B). The major advantage of $B+$ tree is in reducing the number of last level access which would be from disk in case of large data size. 

http://stackoverflow.com/questions/15485220/advantage-of-b-trees-over-bsts

Comments

Sir please answer this question.

The major advantage of B+ tree is in reducing the number of last level access which would be from disk in case of large data size. 

BST is balanced. In BST also we will access the disk only on the last level. Then how is B+ trees better than BST using this argument?

---

because B+ tree has order greater than 2 which reduces the height of tree significantly as compared to any binary tree, and search time is proportional to O(h)

---

@Arjun sir, since the disk access time is very much than that of memory access time and since we are having more locality of reference with B+Trees ,we will be having less reads from the hard disk where is in BST for each cache miss we are going to fetch it from hard disk for each single block..Is it reason we are preferring option B even though disk access time is slower than memory access time?? 

Correct me if I am wrong sir..

Answer 2

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

Data in B+ Tree is stored in a way to make optimum use of locality of reference. And We know that Disk access time (ms) is much higher than memory Access time (ns), So, it takes more time to access a page from Disk, so We want to retrieve as much as data in one go. So, we use B+ Tree instead of BST.

Comments

Data in B+ Tree is stored in a way to make optimum use of locality of reference.

@thor can you explain bit more about this

Answer 3

Binary trees can be skewed. B+ trees are balanced. In binary trees, in the worst case you get $O(n)$ search complexity, while the same for B+ trees is $O(logn)$

Each visit to a node in the tree is actually visiting a block in the Secondary Memory. Since Secondary Memory is slower, B+ trees would benefit us over Binary trees because of the reduction in our visits to the Secondary Memory.

Option B

Answer 4

d)

any other reasonable option is (a), but i chose reliability