Linking Pages In B-Trees

Some time ago I came across one of leetcode issues [1] - to create pointers to next right nodes, given a balanced binary tree.

I decided to find out how this is done in real database systems and took PostgreSQL as an example. Postgres B-Tree indexes are multi-level tree structures, where each level of the tree can be used as a doubly-linked list of pages [2]:

There are differences in Postgres comparing to leetcode assignment:

A structure BTPageOpaqueData holds pointers to both right and left siblings [3].

What does this structure allow a db engine do? When performing index scans, it’s easy and convenient to navigate to left and right pages, without having to start from a root node again and again.

In Postgres' source code, the method responsible for splitting a B-Tree is typically found within the file [4]. This file contains functions related to the insertion of new entries into B-Tree indexes.

The specific function responsible for splitting a B-Tree during insertion is called btsplit [5]. This function is called when a new entry cannot be accommodated within an existing page of the B-Tree due to space constraints. The btsplit function is responsible for splitting the page into two pages and redistributing the entries between them while maintaining the B-Tree’s properties.

As part of the split operation, pointers between the pages are updated.

To summarize, leetcode issue [1] simulates a part of B-Tree’s re-balancing process. The main part of re-balancing is represented by leetcode’s issue [6].