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

11 min readJun 1, 2024--Press enter or click to view image in full sizeGenerated by DALL·ETable of content:Types of indexes in PostgreSQLLogical schema of B-Tree index[Recap] How PostgreSQL stores data ?Logical representation of BTree index in PostgreSQLHow B-Tree index is implemented in PostgreSQLWe’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 PostgreSQLFirst of all, we need to mention about all types of indexes in PostgreSQL. It provides following ones, each using a different algorithm:B-treeHashGiSTSP-GiSTGINBRINEvery index has its own purpose, so in every situation you should choose the one that fits best.Logical schema of B-Tree indexTo 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.B-TreeThis 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.Press enter or click to view image in full sizeComplexityWe 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:Press enter or click to view image in full sizeHow PostgreSQL stores dataLet’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.reltablespaceWHERE relname = 't';Table metadataOID (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.Press enter or click to view image in full sizeHow table data is storedLet’s also take a closer look into how each page is build.Press enter or click to view image in full sizeDiagram of PostgreSQL pagesThe 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 PostgreSQLAn 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:Index metadataAs 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:Press enter or click to view image in full sizeDiagram of how to search in indexLet’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 PostgreSQLLet’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');Press enter or click to view image in full sizeOutput of bt_metap on idx_client indexWe 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);Press enter or click to view image in full sizeOutput of bt_page_stats on idx_clientBtpo_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);Press enter or click to view image in full sizeOutput of bt_page_items on idx_clientThe 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.