B-tree vs. Binary tree

The difference between B-tree and a binary tree is that B-tree is a sorted tree where nodes are sorted inorder traversal whereas binary tree is an ordered tree having a pointer at each node.

Advertisement - Continue Reading Below
B tree vs. Binary tree

Data structures are the most important concepts in computer programing, and in data structures, the two most important concepts are B-tree and Binary tree. Both are different from each other. B-tree is a sorted tree where nodes are sorted in order traversal whereas binary tree is an ordered tree having a pointer at each node.  B-tree and binary tree are non-linear data structures. By name, both terms seem to be the same, but they are not the same as they are different. A binary tree code is stored in RAM whereas a B-tree code is stored in the disk.

B-tree is an M-way tree that is balanced, B-tree is known as balanced sort tree. There is inorder traversal in B-tree. The space complexity of B-tree is O(n). Insertion and deletion time complexity is O(log n). In B-tree, the height of the tree should be as minimum as possible. In B-tree, there should be no empty subtree. All the leaves of the tree should be at same level. Each node can have maximum M number of children and minimum M/2 number of children. Each node in B-tree should have less key than child key.  In B-tree, keys in the subtree present in the left of the key are predecessors. When a node is full, and you try to insert a new node the tree is splited in two parts. You can merge nodes in B-tree until nodes are deleted.

Advertisement - Continue Reading Below

A binary tree has two pointers that contain the address of its child nodes. There are types of binary trees such as a strictly binary tree, complete binary tree, extended binary tree, etc. In the strictly binary tree, there must be left subtree and right subtree, in a complete binary tree, there should be two nodes at each level, and in the threaded binary tree, there should be 0 to 2 number of nodes.  If we talk about transversal techniques, three transversal techniques are in order transversal, preorder transversal, and post order transversal.

Contents: Difference between B-tree and Binary tree

Comparison Chart

BasisB-treeBinary Tree
BasisB-tree is a sorted tree where nodes are sorted inorder traversal.A binary tree is an ordered tree having a pointer at each node. 
StoreB-tree code is stored in the disk.Binary tree code is stored on RAM
HeightThe height of B-tree will be log NThe height of binary tree will be log2 N
ApplicationDBMS is the application of B-tree.Huffman coding is an application od Binary Tree.
Advertisement - Continue Reading Below

B-tree

B-tree is an M-way tree that is balanced, B-tree is known as balanced sort tree. There is inorder traversal in B-tree. The space complexity of B-tree is O(n). Insertion and deletion time complexity is O(log n). In B-tree, the height of the tree should be as minimum as possible.

In B-tree, there should be no empty subtree. All the leaves of the tree should be at the same level. Each node can have a maximum M number of children and minimum M/2 number of children. Each node in B-tree should have less key than child key.  In B-tree, keys in the subtree present in the left of the key are predecessors. When a node is full, and you try to insert a new node the tree is split in two parts. You can merge nodes in B-tree until nodes are deleted.

Binary Tree

A binary tree has two pointers that contain the address of its child nodes. There are types of binary trees such as a strictly binary tree, complete binary tree, extended binary tree, etc.

Advertisement - Continue Reading Below

 In the strictly binary tree, there must be left subtree and right subtree, in a complete binary tree, there should be two nodes at each level, and in the threaded binary tree, there should be 0 to 2 number of nodes.  If we talk about transversal techniques, there are three transversal techniques that are in order transversal, preorder transversal, and post order transversal.

Key Differences

  1. B-tree is a sorted tree where nodes are sorted inorder traversal whereas Binary tree is an ordered tree having a pointer at each node.
  2. B-tree code is stored in disk whereas Binary tree code is stored on RAM.
  3. The height of B-tree will be logN whereas the height of binary tree will be log2 N
  4. DBMS is the application of B-tree whereas Huffman coding is an application od Binary Tree.

Conclusion

In this article above we see the clear difference between B-tree and Binary tree with their implementation.

Explanatory Video

Leave a Comment