B-tree vs. Binary Tree

B-Trees and binary trees are both non-linear data structures and while their names may sound similar, they’re very different in nature. In this article, we will compare them to make them easier to distinguish.

B-Tree

B-tree is a self-balancing tree data structure in which a node can have more than two children. The height of the tree is automatically adjusted on each update in order to keep it evenly balanced. B-tree also keeps the data sorted by storing it in a specific order, the lowest value being on the left and the highest value on the right. It is usually a shallow but wide data structure. While other trees can grow very high, a typical B-tree has a shorter height, even with millions of entries. The typical operations which can be performed on a B-tree are search, insertion, deletion and sequential access.

Based on properties we classify B-trees into different types:

• B-tree: stores keys in its internal nodes but doesn’t need to store those keys in the records at the leaves.
• B+ tree: copies of the keys are stored in the internal nodes while the keys and records are stored in leaves; in addition, a leaf node may include a pointer to the next leaf node which speeds the sequential access.
• B* tree: keep the internal nodes more densely packed by balancing more neighbouring internal nodes. This ensures non-root nodes are fuller – 2/3 instead of 1/2.

B-trees are commonly used in databases or file systems where data is stored externally on disks, which are operating much more slowly than random access memory (RAM) and where keeping the tree shallow is important in order to reduce the number of disk accesses.

Binary Tree

A binary tree is a tree data structure in which each node can have at most two children. They are usually identified as the left child and the right child.  A node without children is called a leaf node. Thus, each node in a binary tree can have either 0, 1 or 2 children. The common operations which can be performed on binary trees are insertion, deletion and traversal. Traversal is the operation in which each node of a tree is visited exactly once in a systematic way.

Based on properties we classify binary trees into different types:

• Full binary tree: where each node can only have zero or two child nodes.
• Perfect binary tree: it is a full binary tree with the additional condition that all leaf nodes (i.e. nodes without children) are at the same level of depth.
• Complete binary tree: where each leaf node is as far left as possible.
• Balanced binary tree: the height of the tree is as small a number as possible.
• Binary Search tree: which keeps the keys in sorted order for fast lookup.

The binary tree is a general concept and various specific types of binary trees can be constructed with different properties and applications. Generally, they are used when records and data are stored in RAM. They can be implemented in expression evaluation and parsers, data compression algorithms, storing router-tables, cryptographic applications, etc.

Key Differences:

• Unlike a binary tree, in B-tree, a node can have more than two children.
• Searching a B-tree is much like searching a binary search tree, but instead of making a binary, or “two-way,” branching decision at each node, we make a multiway branching decision according to the number of the node’s children.
• Inserting a key into a B-tree is more complicated than inserting a key into a binary search tree. A fundamental operation used during insertion is the splitting of a full node around its median key (the middle number in a list of numbers ordered from smallest to largest) into two nodes. Splitting is the way by which the B-tree grows.
• Unlike a binary tree, B-tree increases in height at the top instead of at the bottom.
• Because a range of child nodes is permitted, B-trees do not need re-balancing as frequently as other self-balancing search trees but may waste some space, since nodes are not entirely full. By requiring that all leaf nodes are at the same depth, a B-tree is kept balanced. The depth will increase as more elements are added to the tree, but an increase in the overall depth is infrequent and results in all leaf nodes being one more node farther away from the root. The height of the tree decreases by maximizing the number of keys within each internal node. Also, the number of expensive node accesses is reduced and rebalancing of the tree occurs less often.

Choosing between these two tree structures depends on the memory type which will be used. A binary tree is preferred when records are stored in RAM, which is smaller and faster. B-tree is used when records are stored in a disk, which is larger and slower memory type. B-tree significantly reduces access time due to the high branching factor and the reduced height of the tree.