Search⌘ K
Home
Courses
Deep Dive into the Internals of the Database

B-Tree

Explore how B-trees serve as essential data structures in databases, supporting efficient sorted data storage on disk. Learn the structure of B-trees, their search, insertion, and deletion algorithms, and understand how they minimize disk accesses through high fanout and balanced height.

We'll cover the following...

Introduction

A B-tree is a generalization of a binary search tree that allows multiple keys per node. It addresses limitations of binary and balanced search trees for disk-based storage by reducing the number of disk accesses.

A B-Tree is also called an m-way (or multi-way) tree. Every node in the B-tree can accommodate M-1 keys and M pointers to child nodes. These keys are called separators. A B-tree keeps the keys sorted in ascending order and allows for a binary search:

  • The first child pointer in the node points to the subtree that holds keys lesser than the first key.

  • The last child pointer in the node references the subtree with keys greater than or equal to the final key.

  • Child pointers (other than the first and last in the node) point to the subtree holding keys between the two key ranges Keyi_i−_-1_1 < Keys <= Keyi_i.

The order of a B-tree is the maximum number of children a given B-tree can hold.

Every ...