Deep Dive into the Internals of the Database/

...

/

B-Tree

B-Tree

Learn about the use cases and the mechanics of B-tree insertion, deletion, and search patterns.

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