The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+22 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
asked in Databases by Veteran (52.1k points) | 3.9k views

3 Answers

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

answered by Veteran (413k points)
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)
+23 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.

answered by Loyal (6.7k points)
–6 votes

any other reasonable option is (a), but i chose reliability
answered by Active (3.3k points)

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
49,808 questions
54,489 answers
74,660 users