650 views
3 votes
3 votes
Can somebody please list out the main advantages of B trees, B+ trees and Binary Search Trees over each other?

2 Answers

1 votes
1 votes

B Tree vs Binary Tree

BASIS FOR COMPARISON B-TREE BINARY TREE
Essential constraint A node can have at max M number of child nodes(where M is the order of the tree). A node can have at max 2 number of subtrees.
Used  It is used when data is stored on disk. It is used when records and data are stored in RAM.
Height of the tree logM N (where m is the order of the M-way tree) log2 N
Application Code indexing data structure in many DBMS. Code optimization, Huffman coding, etc.

B Tree vs Binary Search Tree

https://attractivechaos.wordpress.com/2008/09/24/b-tree-vs-binary-search-tree/

B Tree vs B+ Tree

Comparison between B Tree and B+ Tree:

 

B Tree

B+ Tree

Short web descriptions

A B tree is an organizational structure for information storage and retrieval in the form of a tree in which all terminal nodes are at the same distance from the base, and all non-terminal nodes have between n and 2 n sub-trees or pointers (where n is an integer).

B+ tree is an n-array tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children.

Also known as

Balanced tree.

B plus tree.

Space

O(n) 

O(n)

Search

O(log n)

O(logb n)

Insert

O(log n)

O(logb n)

Delete

O(log n)

O(logb n)

Storage

In a B tree, search keys and data stored in internal or leaf nodes.

In a B+ tree, data stored only in leaf nodes.

Data

The leaf nodes of the three store pointers to records rather than actual records.

The leaf nodes of the tree stores the actual record rather than pointers to records.

Space

These trees waste space

There trees do not waste space.

Function of leaf nodes

In B tree, the leaf node cannot store using linked list.

In B+ tree, leaf node data are ordered in a sequential linked list.

Searching

Here, searching becomes difficult in B- tree as data cannot be found in the leaf node.

Here, searching of any data in a B+ tree is very easy because all data is found in leaf nodes.

Search accessibility

Here in B tree the search is not that easy as compared to a B+ tree.

Here in B+ tree the searching becomes easy.

Redundant key

They do not store redundant search key.

They store redundant search key.

Applications

They are an older version and are not that advantageous as compared to the B+ trees.

Many database system implementers prefer the structural simplicity of a B+ tree.

Advantages of B+ trees:

  • 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.
  • The leaf nodes of B+ trees are linked, so doing a full scan of all objects in a tree requires just one linear pass through all the leaf nodes. A B tree, on the other hand, would require a traversal of every level in the tree. This full-tree traversal will likely involve more cache misses than the linear traversal of B+ leaves.

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

Reference:

https://techdifferences.com/difference-between-b-tree-and-binary-tree.html

http://www.differencebetween.info/difference-between-b-tree-and-b-plus-tree

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

0 votes
0 votes
For th same data set order of a node of B+ tree is more(approx 50%) than that of B tree. So this leads to more number of keys values /child pointers can be packed in a each node of B+ tree.Hence the size of B+ tree will be less

 time spent in input/output operations will be less in B+ tree.

 hence B+ tree is preferred over B tree and binary search tree

Related questions

0 votes
0 votes
1 answer
1
aditi19 asked Nov 23, 2018
407 views
can anyone share some good resources fot B+ tree deletion?
0 votes
0 votes
1 answer
2
Akriti sood asked Jan 11, 2017
1,128 views
between B trees and B+ trees,which one is suited for random and which one is suited for sequential access??please explain
3 votes
3 votes
5 answers
4
srestha asked May 22, 2019
1,800 views
Consider the following function height, to which pointer to the root node of a binary tree shown below is passedNote that max(a,b) defined by #define max(a,b) (a>b)?a:b.i...