Introduction to 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.

Introduction to B-tree

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).


  • 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.


  • 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.

Prime Course Trailer

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

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription