GATE CSE 2000 | Question: 1.22, UGCNET-June2012-II: 11
in Databases
41 votes

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

  1. Disk capacities are greater than memory capacities
  2. Disk access is much slower than memory access
  3. Disk data transfer rates are much less than memory data transfer rates
  4. Disks are more reliable than memory
in Databases

1 comment

Plz  explain option A???

Subscribe to GO Classes for GATE CSE 2022

4 Answers

47 votes
Best answer

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.

edited by


"This means that even though in principle a BST might be better in terms of number of memory accesses, the B+-tree and the B-tree can performed better in terms of the runtime of those memory accesses."

I mean how can no of memory access be a yardstick for performance? Only time can be the measuring factor.I am confused with the no of memory access part.Sir could you please explain this statement

Well that is because these people who write standard books know more about the real world problems and assume that they are known to anyone.

In a computer system - at least from 2000 and till now, memory speed is the real bottleneck. That is even if we increase the CPU speed very much, most real world programs won't improve in runtime as the memory speed is the real bottleneck - imagine a neck in a bottle. So, for performance reasons we can consider "no. of memory accesses" as a yardstick.

Now, even with above assumption, in real systems we often have cache which works on the locality of reference.
Got it sir. :)
also sir in terms of memory access how bst is better than b + tree? I agree b+ tree is a form of multilevel indexing, so the memory access time is more,but in bst every time we have to start from the root , and if we have range queries we are saving time here in b+ tree, because we can easily move from one node to another at leaf level for finding the key and corresponding record pointer?
Sir does disk access and disk Transfer rate are related somehow? Disk transfer rate is the rate at which disk is transferring and disk access is amount of time to read/write from disk,Are these related somehow?
^disk access time=seek time+rotational delay+transfer time.

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..

32 votes

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.


1 comment

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

3 votes

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

–6 votes

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

Related questions