Storage: Pages, Heaps & B-Trees

Databases feel abstract because SQL lets you ask for rows without saying where those rows live. Under the hood, PostgreSQL stores tables and indexes as fixed-size pages, uses heap tables for ordinary rows, moves oversized values into TOAST, and uses B-tree indexes as sorted structures that point back to the heap.

This lesson closes the loop between the phone-book index model from Section 16 and the physical objects PostgreSQL exposes through its catalogs. We will not pretend to inspect raw page bytes in the browser; instead, we will use supported catalog and size functions to prove what the engine can honestly show.

Pages: the unit PostgreSQL reads and writes

A page is a fixed-size block of storage. PostgreSQL's default page size is 8 KB, and the live engine reports that directly:

SELECT CAST(current_setting('block_size') AS int) AS block_size_bytes;
 
CREATE TABLE storage_orders (
  order_id int GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  customer_id int NOT NULL,
  note text NOT NULL
);
 
INSERT INTO storage_orders (customer_id, note)
SELECT (g % 10) + 1,
       'receipt-' || lpad(g::text, 4, '0') || '-' || repeat(md5(g::text), 4)
FROM generate_series(1, 1200) AS g;
 
ANALYZE storage_orders;
 
SELECT count(*) AS rows,
       avg(pg_column_size(storage_orders))::numeric(10,1) AS avg_row_bytes,
       pg_relation_size('storage_orders') AS heap_bytes,
       pg_relation_size('storage_orders') / CAST(current_setting('block_size') AS int) AS heap_pages
FROM storage_orders;

 block_size_bytes
------------------
             8192
(1 row)
CREATE TABLE
INSERT 0 1200
ANALYZE
 rows | avg_row_bytes | heap_bytes | heap_pages
------+---------------+------------+------------
 1200 |         177.0 |     229376 |         28
(1 row)

That grid is your first physical picture. The table has 1,200 rows, each row averages 177.0 bytes by pg_column_size, but the heap relation occupies 229,376 bytes: exactly 28 pages of 8,192 bytes. Rows do not get packed into one magical stream of bytes; they live inside pages, with page headers, row headers, free space, and alignment overhead around them.

Two habits follow from this. First, storage questions are usually page questions: "how many rows?" is different from "how many pages must the engine visit?" Second, byte counts in catalogs are allocated storage, not a promise that every byte is filled with your column values. PostgreSQL manages room inside pages so future inserts and updates have somewhere to go.

Heap tables: rows in no key order

A heap table is PostgreSQL's ordinary table storage: rows are placed wherever there is usable space, not sorted by primary key, customer id, or insert-time promise. "Heap" here means unordered storage, not the heap data structure from algorithms class.

The catalog row in pg_class tells you what PostgreSQL registered:

CREATE INDEX storage_orders_customer_idx
ON storage_orders (customer_id);
 
ANALYZE storage_orders;
 
SELECT c.relname AS relation_name,
       c.relkind,
       am.amname AS access_method,
       c.relpages,
       c.reltuples::int AS estimated_rows,
       pg_relation_size(c.oid) AS bytes
FROM pg_class AS c
LEFT JOIN pg_am AS am
  ON am.oid = c.relam
WHERE c.relname IN ('storage_orders', 'storage_orders_customer_idx')
ORDER BY c.relname;

CREATE INDEX
ANALYZE
        relation_name        | relkind | access_method | relpages | estimated_rows | bytes
-----------------------------+---------+---------------+----------+----------------+--------
 storage_orders              | r       | heap          |       28 |           1200 | 229376
 storage_orders_customer_idx | i       | btree         |        2 |           1200 |  16384
(2 rows)

relkind = 'r' is an ordinary table. relkind = 'i' is an index. access_method = 'heap' names the table storage method; access_method = 'btree' names the index method. relpages and reltuples are planner statistics, so they become meaningful after ANALYZE: the table is recorded as 28 pages and about 1,200 rows; the index is 2 pages and points at those same rows.

That separation matters. Creating the index did not sort storage_orders; it created a second relation beside the table. The heap remains the source of complete rows, while the index is an access path the planner may use when its sorted keys match the question. This is why dropping an index can make a query slower without deleting any table data.

Updates add one more wrinkle. PostgreSQL can keep more than one row version around so old readers and new writers can coexist. That version story is MVCC, and 22.3 will take it apart carefully; for today, hold the simple storage picture: ordinary table rows live in heap pages, and indexes point to row locations in that heap.

TOAST: large values move out of line

TOAST stands for "The Oversized-Attribute Storage Technique." It is PostgreSQL's way to keep very large column values from making ordinary heap pages unusable. A table row can keep a compact pointer while the large value is split into chunks in a separate TOAST table.

The payload below is built from many MD5 strings so compression cannot collapse it into a tiny value:

CREATE TABLE storage_documents (
  doc_id int GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  title text NOT NULL,
  body text NOT NULL
);
 
INSERT INTO storage_documents (title, body)
SELECT 'low-compression payload', payload.body
FROM (
  SELECT string_agg(md5(g::text || ':' || s::text), '') AS body
  FROM generate_series(1, 3000) AS g
  CROSS JOIN generate_series(1, 2) AS s
) AS payload;
 
CREATE OR REPLACE FUNCTION lesson_toast_chunk_count(table_name regclass)
RETURNS bigint
LANGUAGE plpgsql
AS $$
DECLARE
  toast_table regclass;
  chunk_count bigint;
BEGIN
  SELECT c.reltoastrelid
  INTO toast_table
  FROM pg_class AS c
  WHERE c.oid = table_name;
 
  EXECUTE format('SELECT count(*) FROM %s', toast_table)
  INTO chunk_count;
 
  RETURN chunk_count;
END;
$$;
 
SELECT pg_column_size(d.body) AS logical_body_bytes,
       pg_relation_size('storage_documents') AS heap_bytes,
       c.reltoastrelid <> 0 AS has_toast_table,
       pg_relation_size(c.reltoastrelid) AS toast_bytes,
       lesson_toast_chunk_count('storage_documents') AS toast_chunks
FROM storage_documents AS d
JOIN pg_class AS c
  ON c.oid = 'storage_documents'::regclass;

CREATE TABLE
INSERT 0 1
CREATE FUNCTION
 logical_body_bytes | heap_bytes | has_toast_table | toast_bytes | toast_chunks
--------------------+------------+-----------------+-------------+--------------
             192000 |       8192 | t               |      204800 |           97
(1 row)

The logical body value is 192,000 bytes. The table heap itself is only 8,192 bytes, while the TOAST table occupies 204,800 bytes across 97 chunks. That is the point: the ordinary row stays small enough to fit cleanly on heap pages, and the oversized value lives out of line until a query actually needs it.

TOAST is also why SELECT * can be more expensive than it looks. A query that only needs doc_id and title can often stay with the compact heap row. A query that asks for body has asked PostgreSQL to reconstruct the large value from its chunks. The answer is the same row either way, but the amount of storage touched can be very different.

B-trees: the phone-book model becomes pages

A B-tree index is a balanced tree of sorted keys plus pointers back to table rows. Section 16's phone-book model still holds: a phone book sorted by last name makes equality and range lookups cheap because you can jump to the right neighborhood, then scan nearby names in order.

The physical version adds pages. A B-tree has a root page, often interior pages, and leaf pages. The leaf pages contain sorted key entries and row pointers. Equality lookups descend through the tree instead of checking every heap page, so the work grows roughly as log(n). Range scans are cheap because once PostgreSQL reaches the first matching leaf entry, nearby leaf entries are already sorted beside it.

One subtlety from 16.2 now becomes concrete: the index stores enough information to find table rows, not necessarily enough information to answer every query alone. Covering and index-only scans are the special case where the needed columns are already available from the index and PostgreSQL can prove the heap visit is unnecessary. The everyday case is index first, heap second.

EXPLAIN (COSTS OFF)
SELECT order_id, customer_id
FROM storage_orders
WHERE customer_id = 7;

                       QUERY PLAN
--------------------------------------------------------
 Bitmap Heap Scan on storage_orders
   Recheck Cond: (customer_id = 7)
   ->  Bitmap Index Scan on storage_orders_customer_idx
         Index Cond: (customer_id = 7)
(4 rows)

Read this with the storage picture in mind. The Bitmap Index Scan searches the B-tree. The Bitmap Heap Scan visits the heap pages that contain the matching rows. Indexes are not a different copy of the result table; they are sorted access paths that help PostgreSQL find heap rows.

Pages, heaps, TOAST, and B-trees are the storage layer the optimizer reasons about. Next, 22.2 moves up one level: statistics, cardinality estimates, and join algorithms — the inputs that decide which access path PostgreSQL chooses.