contador Saltar al contenido

Difference between tree B and binary tree

Tree B and Binary Tree are the non-linear data structure types. Although the terms seem similar but different in all aspects. A binary tree is used when records or data are stored in RAM instead of in disk as the access speed of RAM is much higher than the disk. On the other hand, tree B is used when data is stored in the disk, reduces access time by reducing the height of the tree and increasing the branches in the node.

Another difference between the B tree and the binary tree is that B-tree must have all its child nodes on the same level, while the binary tree has no such constraint. A binary tree can have a maximum of 2 sub-trees or nodes, while in B-tree it can have M no of sub-trees or nodes where M is the order of the tree B.

Comparative graph

Basis for comparison B-tree Binary tree
Essential constraint A node can have at most the number M of child nodes (where M is the order of the tree). A node can have a maximum of 2 subtrees.
Used It is used when data is stored on disk. It is used when records and data are stored in RAM.
Tree height log M N (where m is the order of the M-way tree) log 2 N
Application Structure of code indexing data in many DBMSs. Code optimization, Huffman coding, etc.

Definition of B-tree

A tree B balanced M-way tree and also known as a balanced sorting tree. similar to the binary search tree in which the nodes are organized on the basis of a crossing inorder. The spatial complexity of B-tree O (n). The complexity of the insertion and deletion time O (log n).

There are some conditions that must be true for a B tree:

  • The mast height must be the minimum possible.
  • Above the leaves of the tree, there should be no empty substructures.
  • The leaves of the tree must come to the same level.
  • All nodes should have the least number of children except for leave nodes.

B-tree properties of order M

  • Each node can have the maximum number of children and the minimum number of children or any number between 2 and the maximum.
  • Each node has one less key than children with the maximum M-1 keys.
  • The arrangement of the keys in some specific order within the nodes. All keys in the substructure on the left side of the key are the key predecessors and those on the right side of the key are called successors.
  • When a complete node is inserted, the tree is divided into two parts and the key with median value is inserted into the parent node.
  • The merge operation takes place when the nodes are deleted.

Definition of binary tree

A binary tree is a tree structure that can have at most two pointers for its child nodes. It means that the maximum degree that a node can have 2 and could also be the zero or first degree node.

There are some variants of a binary tree as a strictly binary tree, complete binary tree, extended binary tree, etc.

  • The strictly binary tree is a tree in which each non-terminal node must have left the subtree and the right subtree.
  • A tree called complete binary tree when it satisfies the condition of having 2 nodes i at each level where i is the level.
  • The binary threaded a binary tree consisting of 0 nodes of nodes or 2 numbers of nodes.

Traversal techniques

The tree crossing is one of the most frequent operations performed on the tree data structure in which each node has visited exactly once in a systematic way.

  • Inorder: in this cross tree the left subtree is visited recursively, so the main node is visited and in the last right substructure it is visited.
  • Pre-order In this transverse tree the root node is visited at first, then the left substructure and finally the right subtree.
  • Postorder: this technique visits the left subtree, then the right subtree and finally the root node.

Key differences between tree B and binary tree

  1. In tree B, the maximum number of child nodes that a non-terminal node can have M, where M is the order of tree B. On the other hand, a binary tree can have at most two sub-trees or child nodes.
  2. Tree B is used when data is stored on the disk while the binary tree is used when data is stored in memory as fast as RAM.
  3. Another area of ??application for B-tree the structure of code indexing data in DBMS, in contrast, the binary tree is used in code optimization, huffman coding, etc.
  4. The maximum height of a tree B log M N (M tree order). As against, the maximum height of the binary tree log 2 N (N the number of nodes and base 2 per track).

Conclusion

The B tree is used on binary and binary search tree the main reason behind this memory hierarchy in which the CPU connected to the cache with high bandwidth channels while the CPU connected to the disk through the low width channel of band. A binary tree is used when records are stored in RAM (small and fast) and tree B is used when records are stored in the disk (large and slow). Therefore, the use of the shaft B instead of the binary shaft significantly reduces the access time due to the high branching factor and the reduced height of the shaft.