How I Think About B-tree Indexes in PostgreSQL

B-tree indexes are a very special data structure because they allow efficient searches in tables with millions of rows. However, we can go beyond the usual explanation and look at a practical implementation example: what the “pointer” actually is, what it contains, and how it gives us a clearer picture than the simple phrase “the index has a pointer to the table.”

There is the classic book analogy: in a book, by looking at the index, you can jump directly to the page or pages where the information you need is located. I like that analogy, but I want to emphasize something: an index is not meant to deal with millions of rows. It is actually the opposite. The purpose of an index is to avoid dealing with millions of rows by acting as a fast path to the information.

Ask yourself this: what is the best way to work with a table that has billions of rows?

Think about it…

You will probably think of sharding, partitioning, read replicas, indexes, and other techniques. All of those techniques naturally answer the question. The best way to work with a table that has billions of rows is precisely to avoid working with a table that has billions of rows.

Recap

Before getting into the main topic, I would like to briefly review some PostgreSQL concepts that I consider important.

Page Format

Each table is logically divided into pages. In PostgreSQL, the default page size is 8 KB. A page acts as the minimum read unit: PostgreSQL does not read less than one page.

Super simplified table example

Page Structure

Internally, a page is divided into several areas, but I want to highlight the following three:

Page Structure

1. Header — PageHeaderData

As with everything in life, there is a header that contains general information about the page, such as where there is free space for new tuples and the size of the page itself.

2. Item Pointer Array — ItemIdData

This is an array that works like a table of contents. Inside it, we find the byte offset and the length of each tuple, or row, within the page. This allows us to know the exact location of a tuple and its length.

3. Items — the rows themselves

This is where the actual row data lives.

CTID

The CTID is the physical identifier of a tuple, the famous “pointer.” It is formed by the pair:

(page_number, item_pointer_array_index)

This column exists by default in any table we create.

postgres=# SELECT ctid, * FROM customers LIMIT 10;
  ctid  |   id    | last_name
--------+---------+-----------
 (0,1)  | 4000001 | Rodriguez
 (0,2)  | 4000002 | Miller
 (0,3)  | 4000003 | Miller
 (0,4)  | 4000004 | Rodriguez
 (0,5)  | 4000005 | Davis
 (0,6)  | 4000006 | Brown
 (0,7)  | 4000007 | Davis
 (0,8)  | 4000008 | Johnson
 (0,9)  | 4000009 | Williams
 (0,10) | 4000010 | Rodriguez
(10 rows)

When we create an index, the reference or pointer used by the index is, in fact, the CTID.

This way, PostgreSQL can locate the row directly without doing a sequential scan page by page and row by row. With the CTID, PostgreSQL knows the page number, and since the page size is fixed by default at 8 KB, it can jump directly to that page. Then, using the other part of the CTID, which contains the index inside the item pointer array, PostgreSQL can know the exact byte offset where the tuple is located inside the page.

Direct access to a tuple through CTID and offset from the page pointer array.

Lab

For this lab, we have a customers table with two columns: id and last_name. Both have indexes.

postgres=# \dt customers
           List of relations
 Schema |   Name    | Type  |  Owner
--------+-----------+-------+----------
 public | customers | table | postgres
(1 row)

postgres=# \d customers
                             Table "public.customers"
 Column    |  Type   | Collation | Nullable |               Default               
-----------+---------+-----------+----------+-------------------------------------
 id        | integer |           | not null | nextval('customers_id_seq'::regclass)
 last_name | text    |           |          | 
Indexes:
    "customers_pkey"          PRIMARY KEY, btree (id)
    "customers_last_name_idx" btree (last_name)

To simulate an Index Scan, I will use the pageinspect extension, which lets us inspect PostgreSQL index pages internally. I also have a function called data_to_text() that converts the index value into readable text.

The table contains around 2 million rows. Let’s see what plan PostgreSQL chooses for the following query. I will use LIMIT 1 because the index contains duplicate values, and this will help us later when we observe deduplication behavior.

postgres=# EXPLAIN ANALYZE
SELECT ctid, *
  FROM customers
 WHERE last_name = 'Brow'
 LIMIT 1;

QUERY PLAN
--------------------------------------------------------------------------------------------
 Limit  (cost=0.43..8.41 rows=1 width=17) (actual time=0.043..0.044 rows=1 loops=1)
   ->  Index Scan using customers_last_name_idx on customers
         (cost=0.43..8.41 rows=1 width=17) (actual time=0.042..0.042 rows=1 loops=1)
         Index Cond: (last_name = 'Brow'::text)
 Planning Time: 0.196 ms
 Execution Time: 0.076 ms
(5 rows)

We can see that PostgreSQL uses the index with the condition, and it returns the following result:

postgres=# SELECT ctid,* FROM customers WHERE last_name = 'Brow' LIMIT 1;
    ctid     |   id    | last_name
-------------+---------+-----------
 (10810,151) | 6000001 | Brow
(1 row)

Now, let’s imagine we are looking for the value Smith.

Although I did not mention it before, every B-tree index has a metapage. This metapage tells us the starting page, the root page, and the number of tree levels.

postgres=# SELECT root, level FROM bt_metap('customers_last_name_idx');
 root | level
------+-------
  209 |     2
(1 row)

Here, the root value tells us the page number where the index starts.

The level value tells us the number of levels above the leaf pages. In other words, this index has 3 levels in total: root, intermediate nodes, and leaf nodes.

Let’s inspect the content of root page 209 in the index:

SELECT
    itemoffset,
    ctid,
    data_to_text(data) AS last_name,
    htid,
    tids
FROM bt_page_items('customers_last_name_idx', 209)
ORDER BY itemoffset;

+------------+-------------+-----------+------------+------+
| itemoffset | ctid        | last_name | htid       | tids |
+------------+-------------+-----------+------------+------+
| 1          | (3,0)       |           |            |      |
| 2          | (208,4097)  | Davis     | (2248,58)  |      |
| 3          | (413,4097)  | Garcia    | (4426,28)  |      |
| 4          | (617,4097)  | Johnson   | (6644,160) |      |
| 5          | (821,4097)  | Jones     | (8862,157) |      |
| 6          | (987,4097)  | Martinez  | (8558,97)  |      |
| 7          | (1181,4097) | Miller    | (10097,97) |      |
| 8          | (1343,4097) | Rodriguez | (9504,104) |      |
| 9          | (1540,4097) | Williams  | (396,43)   |      |
| 10         | (1699,4097) | Williams  | (10376,63) |      |
+------------+-------------+-----------+------------+------+

Here, the CTIDs point to index pages. The first entry does not have a value. Since we are looking for Smith, we should choose entry 8 because:

Rodriguez ≤ Smith < Williams

So we descend into index page 1343.

SELECT
    itemoffset,
    ctid,
    data_to_text(data) AS last_name,
    htid,
    tids
FROM bt_page_items('customers_last_name_idx', 1343)
ORDER BY itemoffset;

+------------+-------------+-----------+-------------+------+
| itemoffset | ctid        | last_name | htid        | tids |
+------------+-------------+-----------+-------------+------+
| 1          | (1537,4097) | Williams  | (396,43)    |      |
| 2          | (1340,0)    |           |             |      |
| 3          | (1341,4097) | Rodriguez | (9567,106)  |      |
                         ......
| 23         | (1362,4097) | Smith     | (7,142)     |      |
| 24         | (1363,4097) | Smith     | (69,73)     |      |
| 25         | (1364,4097) | Smith     | (132,136)   |      |
| 26         | (1365,4097) | Smith     | (196,46)    |      |
                         ......
+------------+-------------+-----------+-------------+------+

As we can see, we found an entry with Smith, but we are still at level 2. That means the CTID still points to an index page. However, we can also check the htid column, which points to the tuple in the table.

postgres=# SELECT *
             FROM customers
            WHERE ctid = '(7,142)';

+---------+------------+
| id      | last_name  |
+---------+------------+
| 4001437 | Smith      |
+---------+------------+
(1 row)

Although this index contains duplicates in the leaf pages, the third and final level, we can see how PostgreSQL applies deduplication in the tids column. That column contains all the entries that match the indexed value Smith.

To see this, using entry 23, we go to index page 1362.

postgres=# SELECT
    itemoffset,
    ctid,
    data_to_text(data) AS last_name,
    htid,
    tids
FROM bt_page_items('customers_last_name_idx', 1362)
ORDER BY itemoffset
LIMIT 2;

+------------+-----------+-----------+---------+----------------------------------+
| itemoffset | ctid      | last_name | htid    | tids                             |
+------------+-----------+-----------+---------+----------------------------------+
| 1          | (16,4097) | Smith     | (69,73) |                                  |
| 2          | (16,8324) | Smith     | (7,145) | {"(7,145)","(7,175)",…,"(14,9)"} |
+------------+-----------+-----------+---------+----------------------------------+
(2 rows)

Now we can see that the tids column is no longer empty. It contains a list of CTIDs that satisfy the condition of having the value Smith. This lets us clearly observe deduplication.

If we search for any of those CTIDs:

postgres=# SELECT *
             FROM customers
            WHERE ctid = '(14,9)';

+---------+-----------+
| id      | last_name |
+---------+-----------+
| 4002599 | Smith     |
+---------+-----------+
(1 row)

And that is the end of our artificial index scan — haha!

Now we have a clearer picture of what happens when PostgreSQL decides to use an index. We can also ask ourselves: if I am only searching by last_name, and that value already exists inside the index, do I really need to visit the table?

The answer is no. That is called an index-only scan.

We also saw how deduplication helps save space inside the index.

Note: unique indexes can also contain duplicates because of MVCC. The deduplication behavior in tids follows the same idea.