Binary Tree vs B Tree
Before understanding the differences between the binary tree and btree, we should know about binary tree and btree separately.
What is Binary tree?
A binary tree is a tree that contains at most two child nodes. The binary tree has one limitation on the degree of the node as node in a binary tree cannot contain more than two child nodes. The topmost node in a binary tree is known as a root node and node mainly consists of two sub trees known as left subtree and right subtree. If the node in a binary tree does not contain any children, then it is known as a leaf node. Thus, node can have either 0, 1 or 2 children. The operations that can be performed on a binary tree are insertion, deletion, and traversal.
Binary tree can be categorized into following types:
- Full binary tree: Each node in a binary tree can have zero or two child nodes.
- Perfect binary tree: A perfect binary tree is a full binary tree except one condition that all the leaf nodes exist at the same level of depth.
- Complete binary tree: A complete binary tree is a tree in which all the leaf nodes are left aligned as possible.
- Balanced binary tree: A binary tree is said to be balanced if the height of the tree is as small as possible.
- Binary search tree: A binary search tree is a tree in which all the keys are sorted to provide the faster search.
It can be used to implement the expression evaluation, parsers, data compression algorithms, storing router-tables, cryptographic applications, etc.
What is BTree?
A btree is a self-balancing tree because its nodes are sorted in an inorder traversal. In contrast to binary tree, node in a btree can have more than two children. The height of btree is logMN where M is the order of tree and N is the number of nodes. The height of a btree adjusts automatically, and the height in a btree is sorted in a specific order having the lowest value on the left and the highest value on the right.
Btree is mainly used to store huge amount of data that cannot fit in the main memory. When the number of keys increases then the data is read from the disk in the form of blocks. As we know that disk access time is more than the memory access time. The main idea behind using the btree is to reduce the number of disk accesses. Most of the operations that are implemented on btree like search, delete, insert, max, min, etc have O(h) disk accesses where h is the height of the tree. Btree is a very wide tree. The idea behind constructing the btree by keeping the height of the tree as low as possible by attaching the maximum number of keys in a btree node. The size of the btree node is mainly made equal to the disk block size. Since the height of the tree is quite low so disk accesses are reduced significantly as compared to the balanced binary search tree like AVL tree, Red Black tree, etc.
Some important facts related to btree are given below:
- All the leaf nodes in a btree must be at the same level.
- There should not be exists any empty subtree above the leaf nodes.
- The height of the btree should be kept as low as possible.
In the above figure, we can observe that all the leaf nodes exist at the same level, and all the non-leaf nodes are non-empty sub trees having keys one less than the number of their children.
Let’s understand the differences between binary tree and btree in a tabular form.
| B-tree | Binary tree |
|---|---|
| A node in b tree can have maximum “M’ number of child nodes where M is the order of the tree. | Unlike btree, binary tree can have maximum two children or two subtrees. |
| A btree is a sorted tree because its nodes are sorted in an inorder traversal. | A Binary tree is not a sorted tree A tree can be sorted either in inorder, preorder or postorder traversal. |
| The height of btree is logMN where M is the order of tree and N is the number of nodes. | The height of binary tree is log2N where N is the number of nodes. |
| Btree is implemented when the data is stored in the disk. | Binary tree is implemented when the data is stored in RAM. |
| It is used in DBMS. | It is used in Huffman coding and code optimization. |
| Insertion of data or a key in a btree is more complex than the binary tree. | Insertion of data in a binary tree is easier as compared to btree. |