Understanding B-Tree Indexes in PostgreSQL: A Comprehensive Guide— Part 1

Table of content:

• Types of indexes in PostgreSQL
• Logical schema of B-Tree index
• [Recap] How PostgreSQL stores data ?
• Logical representation of BTree index in PostgreSQL
• How B-Tree index is implemented in PostgreSQL

We’re all familiar with optimizing queries on large tables, especially when filtering operations begin to slow down. However, to truly leverage index effectively, it’s beneficial to understand its internal mechanics. This series of articles delves into the inner workings of the B-Tree index in PostgreSQL and discusses strategies for using this type of index more efficiently.

Types of indexes in PostgreSQL

First of all, we need to mention about all types of indexes in PostgreSQL. It provides following ones, each using a different algorithm:

• B-tree
• Hash
• GiST
• SP-GiST
• GIN
• BRIN

Every index has its own purpose, so in every situation you should choose the one that fits best.

Logical schema of B-Tree index

To start speaking about B-Tree index in Posgtres we need firstly remember what is B-Tree ?

The term “B-Tree” is short for “balanced tree” indicating that the distance between each node and the root is consistent across all levels. Furthermore, the root and its parent nodes can have more than two children, which effectively minimizes the depth of the tree, enhancing search efficiency. Let’s see main aspects about B-Trees:

• Node Flexibility: Nodes can have more than two children, typically varying from a minimum of two to a maximum defined by the tree order (M).
• Height Management: Automatically adjusts to maintain a height of logM N, optimizing search operations.
• Sorting Order: Maintains data in sorted order, ensuring the smallest values are on the left and the largest on the right.
• Uniformity and Efficiency: All leaf nodes are at the same level to ensure efficiency and consistency, and there are no empty subtrees above the leaf nodes.

B-trees are optimized for balance and retrieval efficiency, making them suitable for systems that require frequent data insertions and retrievals, like database indices and filesystems.

This type of index is based on the Lehman and Yao Algorithm, which was developed in 1981. When a simple search is conducted on a table without any indexes, PostgreSQL defaults to a sequential scan. This means it iterates over every data entry in the table, compares them, and if the conditions match, it returns the relevant data. This is an excellent opportunity to illustrate the differences in O complexity with a comparative graph.

We observe that using an index results in quicker information retrieval for larger reads.

[Recap] How PostgreSQL stores data ?

When we create table, we expect that it will be stored in some sort of an ordered data on a disk, but in reality our information can be distributed across different pages and places in that pages.

CREATE TABLE t(
  A INTEGER,
  B INTEGER,
  C VARCHAR
);

For this table physically we will have something like this:

Let’s try to know more about our “t” table.

SELECT class.oid AS "OID", relname AS "Relation Name", 
       schema.nspname AS "Schema", usr.rolname AS "Object Owner", 
       coalesce(tblsp.spcname, 'pg_default') AS "Tablespace", 
       relpages AS "Amount Pages", reltuples AS "Amount Tuples", 
       reltoastrelid AS "TOAST table", 
       CASE 
          WHEN relpersistence = 'p' THEN 'Permanent' 
          WHEN relpersistence = 't' THEN 'Temporary' 
          ELSE 'Unlogged' 
        END AS "Type", 
        pg_relation_filepath(class.oid) AS "File Path", 
        pg_size_pretty(pg_relation_size(class.oid)) AS "Relation Size" 
FROM pg_class class INNER JOIN pg_namespace schema 
                    ON schema.oid = class.relnamespace 
                    INNER JOIN pg_authid usr 
                    ON usr.oid = class.relowner 
                    LEFT JOIN pg_tablespace tblsp 
                    ON tblsp.oid = class.reltablespace
WHERE relname = 't';

OID (Object Identifier) is an identifier created within PostgreSQL, based on a system sequence. This sequence ensures that each new object we create — whether it be a column, function, trigger, virtual table, or something else — receives a unique identifier. This unique identifier allows us to reference the object unambiguously.

What else should be noted in a query?

• Firstly, there is the default tablespace, which in PostgreSQL is pg_default.
• The schema is public by default.
• The owner of the table is the individual who created it and is responsible for managing access to it.
• There are columns that indicate the number of pages and rows — tuples.
• The concept of TOAST tables or auxiliary tables also exists. These tables support the main table and allow you to split long rows if they do not fit within a specific page based on a particular strategy or policy.
• There are various types of tables. We are currently considering a regular (permanent) journaled table, which is created using the CREATE TABLE command.
• Lastly, there is the file path of the table — the path mapped at the operating system level in pg_home, where your PostgreSQL instance resides.

In the file path, you see a file named 16389. This binary file contains the content of your table (if you insert, update, or delete data). Note that this file matches the table’s OID, establishing a one-to-one correspondence between the file name on disk and its unique identifier.

Since no data has been inserted into the table, the relation size is 0 bytes.

In PostgreSQL, data is stored in files on disk. For tables smaller than 1 GB, each table’s data is stored in a single file. However, for tables larger than 1 GB, PostgreSQL splits the data into multiple files, each up to 1 GB in size. This allows efficient management and access to large datasets.

Let’s also take a closer look into how each page is build.

The structure of a page grows both from the top down and from the bottom up. When you insert data, tuples (T1, T2, T3) are created and written from the bottom left. They grow until they meet pointer values (I1, I2, I3) closer to the start of the page.

Pointers are references to specific tuples stored lower in the file. This structure has been thoroughly optimized and proven for efficient information storage. It aids the PostgreSQL optimizer in effectively working with offsets and pointers.

A page has a header, a meta-layer that stores the total space available in the page. Additionally, the page structure includes transaction pointers and a meta-layer for each tuple and row. There is also a special zone, which is not used for regular tables but is necessary for index structures. This is because the page serves as an atomic element not only for tables but also for indexes. This unified structure supports various storage needs.

Also, it’s good to mention about ctid. In PostgreSQL, ctid is a unique identifier for each row (tuple) within a table. It represents the physical location of the tuple within the table's storage file. The ctid consists of a pair of numbers: the block number and the offset within that block. With help of ctid we can access any specific row in the table. By adding OID relationships, we essentially get coordinates for locating information. On one side, we have the data file; on the other, we have the page within this data file; and, finally, we have the tuple where the specific information is stored within the page.

This principle underlies btree indexes, where the leaves in the btree index point to specific ctids in particular files.

Logical representation of BTree index in PostgreSQL

An index structure in PostgreSQL is a separate data file that resides alongside or near the table’s data file. It can be placed nearby because we can create a separate tablespace specifically for storing the index. When an index is created, the database records its details in the metadata, including the location and path of the corresponding index file.

The command to create a standard B-Tree index is as follows:

CREATE INDEX index_name ON table_name (column_name);

Here we create index with name index_name on table with table_name on column column_name .

If we create index on our table and use query with param of index name relname="index_name" , we will get next info:

As we can see, page is utilized for different structures in PostgreSQL.

Now let’s look at the logical representation of a B-Tree index. We have a table containing arbitrary rows, which may be in a disordered state and not necessarily sorted. The tree built based on the index can be illustrated as follows:

Let’s imagine we are searching for the number 37. We start at the root and compare: is 13 greater than 37? No, so we move to the right. Next, we reach another node where we must decide where to go next. In this example, 37 lies between 31 and 41. We proceed to the corresponding node at the third level, where we can find the address of the row that matches the search element 37. We then go to the specific page and record on that page to retrieve the information, avoiding a full table scan.

How B-Tree index is implemented in PostgreSQL

Let’s assume we have the following table and index:

CREATE TABLE IF NOT EXISTS public.client (
 id int,
 name varchar
);
CREATE INDEX idx_client ON public.client (id);

For investigation of under the hood processes we will use pageinspectextension.

Important PRIMARY KEY and UNIQUE constraints create index by default.

CREATE EXTENSION IF NOT EXISTS pageinspect;
INSERT INTO public.client VALUES (1, 'Row #1');
SELECT *
FROM bt_metap('idx_client');

We received metadata — various technical information, as well as information about the page that serves as the root. This is fastroot, explaining how one can proceed in further searches, developing the tree’s topology.

In our case, fastroot equals 1, which is assumed to be the page number of the index. Let’s take a look at this page using the bt_page_stats function, which returns page statistics for the B-Tree index:

SELECT *
FROM bt_page_stats('idx_client', 1);

Btpo_prev and btpo_next indicate whether our page has a page to the left or right. Type L, meaning leaf, is defined as such because there is exactly one record in our table. This means that our root also acts as a leaf. In the live_items column, we see live elements, the value is 1, because we made one INSERT.

To see which specific elements are contained in this single page, we use the bt_page_items function:

SELECT *
FROM bt_page_items('idx_client', 1);

The function returns our one live record. Each record has its own ctid — this is the address we need to go to for further examination. It also contains data corresponding to the bigint type, which is 8 bytes.

Let’s go further and insert multiple rows and try to inspect our index.

TRUNCATE TABLE public.client;
INSERT INTO public.client
SELECT i, 'Row #'||i::VARCHAR
  FROM generate_series(1,1000) AS k(i)
SELECT *
FROM bt_metap('idx_client');

Let’s look into first node:

Now, type is not a leaf but root. Let’s also take a look into items:

Need to emphasize that the ctid addresses here are not addresses in the data files, but rather addresses on the pages within the index itself. We are at the root, and the root contains the address state of the nodes located beneath it.

If we examine the data, the second element is 367, converted to a standard numbering system, and the last element on our page is 733.

To clarify: From the root, there are three leaves — 1, 2, and 4. Each leaf corresponds to specific ranges of values: the first leaf covers 0 to 366, the second from 367 to 732, and the third from 733 onwards.

Let’s take a closer look to page #1:

Here we can see that type now is L- leaf. The statistics also include a history for the previous and next leaf — btpo_prev and btpo_next.

A zero indicates that there is no leaf on the left. The page on the right is #2, which corresponds to the next page in the sequence. In this case, a bridge is formed: page #1 knows that page #2 holds the next range.

If we look at the elements of the concrete page:

We observe a traversal from one to 367 of live record values. The very first record is known as the high key, which marks the boundary: up to which element all other elements are stored. The indexed data itself starts from the second element after the high key, covering elements 2, 3, 4, and so on, up to the 367th row or the 366th element.

What we have isn’t exactly a tree. By definition, a tree is a structure with a root, intermediate states as nodes, and leaves. However, if the leaves are interconnected, it’s no longer a tree but a directed graph. These connections, or “bridges,” are essential for optimization — they prevent the constant need to return to the root to locate subsequent elements. To traverse all leaves, one must jump from one page to another. These bridge pointers help the optimizer understand where to go next. While you could return to the root each time — to realize, for instance, that the 366th element ends on page one and the 367th is on page two — it’s more efficient to use the pointers and move to the next states without repeatedly returning to the root.