Access methods

PostgreSQL has two layers of pluggable access methods: the Table Access Method API for row storage, and the Index Access Method API for indexes. Both are registered in pg_am and dispatched through function pointer tables at runtime. Source: src/backend/access/.

Directory layout

src/backend/access/
├── brin/        # Block Range INdex
├── common/      # shared utilities (heap tuple deforming, toast, reloptions)
├── gin/         # Generalized INverted index
├── gist/        # Generalized Search Tree
├── hash/        # hash index
├── heap/        # heap (the only Table AM)
├── index/       # generic index AM dispatch
├── nbtree/      # B-tree index
├── rmgrdesc/    # WAL record description hooks (per AM)
├── sequence/    # sequence access (CREATE SEQUENCE)
├── spgist/      # Space-Partitioned GiST
├── table/       # generic Table AM dispatch + toast helpers
├── tablesample/ # TABLESAMPLE methods
└── transam/     # transaction manager, WAL, CLOG, multixact, SLRU

Table access methods

A table access method exposes a uniform "rows in, rows out" API. The interface lives in src/include/access/tableam.h (TableAmRoutine struct). Source: src/backend/access/table/tableam.c for dispatch, src/backend/access/heap/heapam_handler.c for the heap implementation.

typedef struct TableAmRoutine
{
    NodeTag     type;
    /* slot operations */
    const TupleTableSlotOps *(*slot_callbacks)(Relation rel);
    /* scan */
    TableScanDesc (*scan_begin)(Relation rel, Snapshot snapshot, ...);
    bool        (*scan_getnextslot)(TableScanDesc scan, ScanDirection dir, TupleTableSlot *slot);
    /* tuple operations */
    void        (*tuple_insert)(Relation rel, TupleTableSlot *slot, ...);
    TM_Result   (*tuple_update)(Relation rel, ItemPointer otid, TupleTableSlot *slot, ...);
    TM_Result   (*tuple_delete)(Relation rel, ItemPointer tid, ...);
    /* ... many more callbacks ... */
} TableAmRoutine;

The only in-tree implementation is heap. It is the default for all tables created without a USING <am> clause and is what most code paths actually exercise. Pluggable table AMs were introduced primarily to let extensions experiment (zheap, OrioleDB, etc.); none ship with core.

Heap

Source: src/backend/access/heap/.

On-disk layout

A heap page is 8 KB:

+----------------+
| PageHeaderData | 24 bytes
+----------------+
| ItemId array   | grows down
| ...            |
+----------------+
| (free space)   |
+----------------+
| ...            |
| HeapTuples     | grow up
+----------------+
| Special area   | (empty for heap; used by indexes)
+----------------+

PageHeaderData (src/include/storage/bufpage.h) carries the page LSN, checksum, free space pointers, and flags. Each ItemId (line pointer) holds the offset, length, and state flag of a tuple slot. Tuples grow from the bottom; line pointers from the top; free space sits in the middle.

A HeapTuple (src/include/access/htup.h, htup_details.h) has:

• t_xmin, t_xmax — inserting/deleting transaction IDs.
• t_cmin/t_cmax — command IDs (collapsed into one word).
• t_ctid — self-pointer or "this row was updated to N" link.
• t_infomask, t_infomask2 — flags (committed, NULL bitmap present, hot-updated, ...).
• t_hoff — header length.
• The user data, with optional NULL bitmap and OID (legacy).

Heap operations

Operation	Source	Notes
heap_insert	heapam.c	Find a target page (via FSM), pin, lock, insert, WAL-log, mark dirty.
heap_update	heapam.c	Mark old tuple's xmax, insert new version, link via t_ctid. May qualify for HOT.
heap_delete	heapam.c	Mark tuple's xmax.
heap_fetch	heapam.c	Fetch a specific tuple by TID.
heap_getnext	heapam.c	Sequential scan; respects snapshot via HeapTupleSatisfiesVisibility.
heap_multi_insert	heapam.c	Bulk insert (used by COPY).
heap2_redo / heap_redo	heapam.c, heapam_xlog.c	WAL replay during recovery.

Visibility

Whether a tuple is visible to a snapshot is determined by HeapTupleSatisfiesVisibility in src/backend/access/heap/heapam_visibility.c. The function dispatches on the snapshot type (MVCC, dirty, self, etc.) and tests t_xmin/t_xmax against the snapshot, consulting CLOG to find out if the relevant XIDs committed.

TOAST

Wide values (>≈2 KB) are pushed out of the main heap into per-table TOAST tables. Source: src/backend/access/common/toast_*.c, src/backend/access/table/toast_helper.c. A TOAST pointer in the heap row references one or more chunks in pg_toast.pg_toast_<oid>, which is itself a heap table.

HOT (Heap-Only Tuples)

When an UPDATE modifies no indexed column, the new version can be placed on the same page and chained off the old one without inserting any index entries. This is Heap-Only Tuple updating; it dramatically reduces index churn. Source: heapam.c::heap_update, heap_hot_search_buffer. A "single-page HOT chain" is collapsed during page pruning (heap_page_prune, heap_page_prune_opt).

Index access methods

Indexes follow a parallel API. The interface is IndexAmRoutine in src/include/access/amapi.h. Each index AM provides build, insert, scan, and vacuum callbacks.

AM	Source	Use case
B-tree	src/backend/access/nbtree/	The default. Equality and range queries on ordered types.
Hash	src/backend/access/hash/	Equality only. Now WAL-logged (was not pre-10).
GIN	src/backend/access/gin/	"Generalized Inverted Index" — sets of small values per row. Backbone of full-text search and JSONB containment.
GiST	src/backend/access/gist/	"Generalized Search Tree" — extensible, used for geometric, range, and trigram indexes.
SP-GiST	src/backend/access/spgist/	Space-partitioned GiST. Tries, quad-trees, k-d trees.
BRIN	src/backend/access/brin/	Block Range INdex. Tiny indexes that summarize ranges of pages — useful for naturally clustered data (e.g., time-series).

B-tree

The most heavily used index. Source: src/backend/access/nbtree/. Implements the Lehman-Yao algorithm with project-specific extensions:

• High keys, right links between sibling pages.
• Concurrent inserts/splits without root-locking.
• Deduplication of equal keys (introduced in 13).
• Skip scans on multi-column indexes (recent work; see nbtsearch.c, nbtutils.c).

nbtsearch.c implements the descent and scan; nbtinsert.c the insertion (with split logic in _bt_split); nbtxlog.c the WAL records.

GIN

src/backend/access/gin/. Each indexed value is broken into "keys" (e.g., the words in a tsvector or the elements of an array). The index is a B-tree of keys, with each leaf pointing at a posting list (or a posting tree, for hot keys) of TIDs.

GIN supports partial-match queries (substring search via pg_trgm) and consistent-function-based custom operators. The pending list (gin/ginfast.c) defers insertions to amortize cost — a recent insert may not be in the main tree yet but in a pending list at the metapage.

GiST and SP-GiST

Generic frameworks for indexes that don't fit B-tree's total-order assumption. The user (or extension) supplies operator-class methods that define how to:

• Pick a child page during insertion (picksplit).
• Compute a "consistent" answer for a search predicate.
• Compute a "union" of child page bounds.

btree_gist, btree_gin, and PostGIS's spatial indexes are all built on these. SP-GiST adds space-partitioned variants — quad-trees, k-d trees, suffix trees.

BRIN

src/backend/access/brin/. Stores summary "tuples" — one per range of pages — instead of indexing each row. Tiny on disk; useful when data is correlated with physical layout (e.g., a created_at column where rows are inserted in time order). Range-summary opclasses: minmax, inclusion, bloom, minmax-multi.

Hash

src/backend/access/hash/. A bucket-based hash index, WAL-logged since 10. Useful for equality-only access on types that don't sort cleanly. Less popular than B-tree because B-tree handles equality just fine.

Sequences

src/backend/access/sequence/seqlocalam.c plus the legacy src/backend/commands/sequence.c together implement CREATE SEQUENCE. A sequence is a single-row relation with its own access method, providing nextval, currval, setval semantics.

Tablesample

TABLESAMPLE is a SQL-standard sampling extension. Methods (SYSTEM, BERNOULLI, plus contrib's tsm_system_rows and tsm_system_time) are registered as table-sampling AMs. Source: src/backend/access/tablesample/.

Transaction manager (transam)

Sits in src/backend/access/transam/ next to the access methods because it is what makes their durability and isolation work. Subsystems:

• xact.c — top-level transaction state machine (StartTransaction, CommitTransaction, AbortTransaction, savepoints, two-phase commit driver).
• xlog.c — write-ahead log: record assembly, WAL buffer flush, recovery driver.
• xloginsert.c — XLogInsert API used by every page-modifying access method.
• clog.c, multixact.c, subtrans.c, commit_ts.c — SLRU caches that record per-XID commit/abort, multi-XID groupings, sub-transaction parents, and commit timestamps.
• slru.c — generic SLRU page cache used by all four.
• varsup.c — XID and OID counter management; wraparound prevention.
• twophase.c — PREPARE TRANSACTION / COMMIT PREPARED durability.

These are covered in more detail under MVCC and transactions and WAL and recovery.

Entry points for modification

• Add a tuple flag: t_infomask bits in src/include/access/htup_details.h. Many bits are already used; check before grabbing one.
• Add an index AM: implement the IndexAmRoutine callbacks, register it in pg_am (src/include/catalog/pg_am.dat), and provide an opclass.
• Touch B-tree internals: nbtinsert.c for inserts, nbtsearch.c for scans, nbtxlog.c for recovery records.
• Add a Table AM (rarely a wise patch direction): implement TableAmRoutine and register a handler. The heapam_handler.c file is the reference implementation.

For the storage layer beneath this, see Storage. For how the planner picks an index, see Planner.