What is the difference between B tree and B+ tree in data structure?

This entry was posted in DATA STRUCTURE on by

B-Tree

M-way tree provides the shorter search path lengths as compared to binary tree. A very important category of m-way trees is B-tree which was introduced by R.Bayer and E. Mc Greight in year 1970’s.  Faster access to the data set is very important if the data set contains a very large number of records that are to be sorted on the secondary storage devices. For organizing such a large data set, indexing is required which provides the information about the location of the records with some key. Slurs. Such an indexed organization is B-tree in which each node of the tree may contain more than one key depending upon the order of the B-tree.


B-tree of order m has following properties:

  • Each node of the tree except root node and leaf nodes, has maximum of m children and minimum of m/2 children.
  • In other words, each node of the tree except root node must have maximum of m – 1 keys and minimum of (m/2) -1 keys.
  • All leaf nodes in B-tree must be on the same level.
  • The key values in each node are stored  in ascending order.
  • The key in a node separates the ranges of keys which are stored in each child node of that node.

For example:

A B-tree of order 3 is known as 2-3 tree and a B-tree of order 4 is known as 2-3-4 tree.

Maximum number of elements in B-tree of order m and height h.

Level 0 contains m-1 elements

Level 1 contains m(m-1) elements

Level 2 contains m^2(m-1) and so on..

 

B+ Tree

B+ tree is better used when the records are required to be accessed randomly as well as sequentially. Being a non-linear indexed structure, the records can be accessed randomly just like the B-tree.

It has order m properties:

  • Each node of the tree except root node and leaf nodes, has maximum of m children and minimum of m/2 children.
  • In other words, each node of the tree except root node must have maximum of m – 1 keys and minimum of (m/2) -1 keys.
  • All leaf nodes in B-tree must be on the same level.
  • The key values in each node are stored  in ascending order.
  • The key in a node separates the ranges of keys which are stored in each child node of that node.
  • All the internal/non-leaf nodes contain only the keys not the data associated with these keys. Data can be found only in the lead node. It means, to find the data, we have to travel to the leaf node.
  • All leaf nodes are linked together as a double-linked list so that the file can be accessed sequentially.




Leave a comment