B-Trees Under the Hood: How PostgreSQL Indexes Actually Work

Krishnasrivastava

6 min read

·

Oct 8, 2026

--

Listen

Share

Many of you know that SQL based databases such as postgress etc. use B-Tree for storing indexes , but how many of you really know the internal mechanism and operations that are done in it like , — insertion , deletion and searching .

How the searching takes roughly log(n) time instead it the sequential search time complexity of O(n).

Is the postgress B-Tree similar to the B-Tree that we study in our basic DSA curriculum or there are some more aspects to it ?

lets find out these answers in this small blog .

Firstly , what is a B-Tree ?

A B-tree is a self-balancing multi-way search tree in which each node can contain multiple keys and have multiple children .Value smaller than the parent node will be found on the left child traversal and all the nodes that are greater than the parent node will be found in the right child traversal .

Now let us understand why indexes are stored in this type of data structure .
Suppose we have a users table

CREATE TABLE users (
id SERIAL PRIMARY KEY,
age INT,
name TEXT
);

In this table , postgres automatically index over the unique id that is the “id ” or “user_id” accordingly.

Whenever , we create indexes on postgres —
CREATE INDEX idx_users_age ON users(age),

supposing we have id’s : [10 , 20 , 30 , 40 , 50] , each node in the B-tree stores multiple id’s according to their storage limit .

hence , it is cleared that what is a B-TREE and how we store indexes in B-TREE , but the question arises that why postgres use this B-Tree and does it use it in the same way ?

lets find out…

Why B-Tree and What PostgreSQL actually stores in a B-tree index ?

Imagine you have millions of records and you have to search one particular row then you to search millions of rows sequentially to retrieve one particular row which constitutes to the O(n) time complexity , which is not bad but slower when the data is very large .
What if you had a specific region to look into , a smaller search space .

Here comes the B-Tree ,
In a B-Tree we know that all the elements in the left are amller than the parent and all the elements in right sub-tree are bigger than the parent.
Here we can easily eliminate the half records , just by comparing the query with the root node .
When you repeatedly eliminate large portions of the search space it gives us a time complexity of O(log(n)) which is blazing fast.

But there’s an even more important reason PostgreSQL uses B-trees:
They are designed around disk pages.

PostgreSQL doesn’t think in terms of individual nodes
When you learn B-trees in DSA, you might imagine:

But PostgreSQL stores index data in pages. So instead of storing
Node
├── key
├── key
├── key
think it like :
B-tree page
┌─────────────────────────────┐
│ key │ pointer │ key │ … │
│ key │ pointer │ key │ … │
└─────────────────────────────┘

Here , each B-Tree node corresponds roughly to an index page.
For an example:

Here , multiple children / pages are inserted under a parent and follows the B-Tree structure hence we can say that postgree B-TREE are design around disk pages , it still follows the basic principle of a B - Tree , just what the node stores and its structure got enhances from the basic B-tree that we study in DSA.

So, now as we saw why and how the B-TREE is used in this context , let us come to the interesting part , that are the operations like insertion , deletion etc.

Insertion

suppose our tree be like :

now we insert “ INSERT INTO users(age) VALUES(25); ”
Postgres will search in the tree that where does the 25 belongs , we know that 25 < 50 , so we will go to the left sub-tree , this node stores [10 ,20 ,30]
now here , comes two interesting cases :

1. If the node capacity is available , then the node automatically gets stored in the left leaf node like : [10 , 20 , 25 , 30]

2. If the node capacity is already full , Postgress identifies that 25 < 50 hence the page where it should be stored is the left leaf but the left leaf page is already full , in that case “PAGE SPLIT” takes place.

what is a page split?

whenever the capacity of a page is full , page split happens .
Before:

[10,20,30,40]

conceptually insert 25 in the given page: [10 , 20 , 25 , 30 , 40]
now the page exceeded its limit so split it into 2 pages :
[10 , 20 , 25] and [30 , 40]

Now the parent needs to know that there is another child page and also we need a separator to identify that “If you are looking for values ≥ some boundary, go to the new right page.”

So a separator is inserted into the parent.

30 is not being moved from the leaf to the parent in the same way a normal B-tree textbook diagram might suggest.
For PostgreSQL’s B-tree, the parent gets a downlink/separator information associated with the new right page.
The leaf still contains :[30 , 40]
here , 30 as a separator to parent is just the boundary for deciding which child page to visit.
hence afterwards , the tree looks like :

But what if the parent and children all pages are full ?

And in this very much case , the B-TREE grows upwards , forming a new root by splitting the parent page , The root splits , a new root is created by growing the tree upwards.
The core concept still stays the page split

And , this can happen recursively , This is the beautiful property of B-trees.
This is not the actual process how Postgress handles pages , but it is the correct mental model of the process

Press enter or click to view image in full size

In a similar way deletion happens from the pages

Deletion

Deletion in a B-tree starts by locating the index entry in the appropriate leaf page and removing it. If this causes a page to become empty or no longer useful, PostgreSQL can perform cleanup and page deletion, updating the parent page accordingly. In textbook B-tree implementations, deletion may also involve borrowing keys from a sibling or merging underfull nodes. PostgreSQL’s implementation is more sophisticated and does not simply merge pages whenever they become underfull, but the core idea remains the same: remove the unnecessary index entry while keeping the B-tree structure valid and efficient.

Everything i told in this article is a miniature mental model for the working of B-Trees in PostgresSql
The real working is a little complicated involving good concepts of Operating system and disk page management

Press enter or click to view image in full size

But , for the B-TREE part , the current mental model is sufficient .