Year-End Discount: 10% OFF 1-year and 20% OFF 2-year subscriptions!

Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

definition
b-tree
data structures

What is a B-Tree?

Educative Answers Team

Tired of LeetCode? ūüė©

Learn the 24 patterns to solve any coding interview question without getting lost in a maze of LeetCode-style practice problems. Practice your skills in a hands-on, setup-free coding environment. ūüí™

A B-Tree is a self-balancing m-way tree data structure that allows searches, accesses, insertions, and deletions in logarithmic time. Each node in a B-Tree of order m can have, at most, m children and m-1 keys.

Think of B-Tree as a generalization of a binary search tree (BST). Similar to a BST, the stored data is sorted in a B-Tree, but unlike a BST, a B-Tree can have more than two child nodes.

svg viewer
A B-Tree with order 3

In addition to having multiple children, each node in a B-Tree can have more than one key, which keeps the height of the tree relatively small. Later on, we will see how keeping multiple keys in a single node helps with data locality‚Äč.

In summary, a B-Tree of the order m has the following properties:

  • each node has at most m children
  • a node with n children must have n-1 keys
  • all leaf nodes are at the same level
  • every node, except the root, is at least half full
  • root has at least two children if it is not a leaf

Time complexity

The time complexity for insertion, deletion, and search operations takes O(log n)O(log \space n) time where nn is the number of keys stored in the tree.

Space complexity

The space complexity for a B-Tree is O(n)O(n),‚Äč where nn is the number of keys in the tree.

Uses

B-Tree is primarily used to store data on disk because its operations (e.g., insert and search) require relatively few disk reads.

Often the size of data on the disk is large and cannot fit entirely in main memory. Hence, data is read from a disk in contiguous chunks or blocks.

svg viewer
Now that's a fat tree!

However, reading from a disk is costly as disk access times are far higher than memory access times.
B-Trees have a high branching factor, meaning the trees are fat with a relatively small height, which ensures minimal disk reads to navigate‚Äč to the place where the data is stored.

B-Trees are, therefore, well-suited for storage systems that read and write large blocks of data.

svg viewer

RELATED TAGS

definition
b-tree
data structures
Copyright ©2022 Educative, Inc. All rights reserved

Tired of LeetCode? ūüė©

Learn the 24 patterns to solve any coding interview question without getting lost in a maze of LeetCode-style practice problems. Practice your skills in a hands-on, setup-free coding environment. ūüí™

Keep Exploring
Related Courses