# Introduction to B-Trees

## B-Trees

In this article, we will learn Introduction to B-Trees. B-Tree is a self-balancing search tree. The main idea of using B-Trees is to reduce the number of disk accesses. The height of B-Trees is kept low by putting maximum possible keys in a B-Tree node.

## Introduction to B-Trees

B-Tree is a self-balancing search tree. Generally, a B-Tree node size is kept equal to the disk block size.As height is low for B-Tree, total disk accesses for most of the operations are reduced significantly compared to other search trees.

### Properties of B-Tree

• All leaves are at same level.
• A B-Tree is defined by the term minimum degree ‘n’. The value of n depends upon disk block size.
• Every node except root must contain at least n-1 keys. Root may contain minimum 1 key.
• All nodes (including root) may contain at most 2n – 1 keys.
• Number of children of a node is equal to the number of keys in it plus 1.
• All keys of a node are sorted in increasing order. The child between two keys k1 and k2 contains all keys in the range from k1 and k2.
• B-Tree grows and shrinks from the root.
• Time complexity to search, insert and delete is O(logn).

### Search

• Let the key to be searched be k.
• We start from the root and recursively traverse down.
• For every visited non-leaf node, if the node has the key, we simply return the node.
• Otherwise, we recur down to the appropriate child (the child which is just before the first greater key) of the node.
• If we reach a leaf node and don’t find k in the leaf node, we return NULL.

### Traverse

• Traversal is also similar to in-order traversal of Binary Tree.
• We start from the leftmost child, recursively print the leftmost child, then repeat the same process for remaining children and keys.
• In the end, recursively print the rightmost child.

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others