3,899 views
0 votes
0 votes
I am unable to get that what advantage do we get when we store only records consisting of primary attributes in case of B+ tree i.e. we do not store record pointers corresponding to those key attributes , we do it only at the leaf level , doesn't it increase the overhead since we have to come upto the leaf level and then access the data where as in case of B tree with each node we have a record pointer associated so I guess that's more advantageous , so then why database designers prefer B+ trees over B trees ?

2 Answers

Best answer
2 votes
2 votes
first of all u need to understand this.  we do not use AVL trees or red black trees as they grow depth wise rather than breath wise. we prefer breath growth as the number of levels will be less and the time search time will be less due to less number of levels.

now we prffer b+ over b because . b+ grows more breath wise than b tree.  what it means is it can  holds more data in internal nodes.

to explain i m taking an informal example

suppose u have a seat which is of 6 meter. now each person requires 1m space . so total number of person that can sit =6 (b+ tree case)

now in second case everyone is carrying an extra luggage of 1 meter. so total number of person that can sit =3 (b tree case)

the same case happens in b tree. every internal node should contain key with record pointer . which is a type of extra field.which is not present in b +tree . due to which the number of keys a block can accumulate becomes less. and the b+ tree for the same reason can accumulate more number of keys. as more number of keys can be stored in the internal nodes . the height of tree decreases due to which the search efficiency increases.

2ndly page fault decreases . as in one page more number of keys are stores the page fault rate decreases as there is more probability of a hit.

now i think u can understand this rather than mugging up.
1 votes
1 votes
the advantage of using b+tree over b treee is that all the data is present in the leafs of a b+ tree. so if we just run a traversal on the leafs nodes only we will get the sorted order directly, which will be linear where as we have to do a full traversal of tree in b tree.

2nd ly 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.

Related questions

1 votes
1 votes
0 answers
1
0 votes
0 votes
1 answer
3
Isha Gupta asked Jun 12, 2016
1,715 views
which commands are used to control access over objects in relational database
0 votes
0 votes
1 answer
4
Salazar asked Jan 29, 2018
3,934 views
Maximum height of a B+ tree of order m with n key values is (With Derivation), the answer is known Logceil(m/2) NI tried deriving but had some trouble, could someone assi...