Map</primary>
</indexterm>
<indexterm><primary>FSM</primary><see>Free Space Map</see></indexterm>

<para>
Each heap and index relation, except for hash indexes, has a Free Space Map
(<acronym>FSM</acronym>) to keep track of available space in the relation.
It's stored alongside the main relation data in a separate relation fork,
named after the filenode number of the relation, plus a <literal>_fsm</literal>
suffix. For example, if the filenode of a relation is 12345, the
<acronym>FSM</acronym> is stored in a file called
<filename>12345_fsm</filename>, in the same directory as the main relation file.
</para>

<para>
The Free Space Map is organized as a tree of <acronym>FSM</acronym> pages. The
bottom level <acronym>FSM</acronym> pages store the free space available on each
heap (or index) page, using one byte to represent each such page. The upper
levels aggregate information from the lower levels.
</para>

<para>
Within each <acronym>FSM</acronym> page is a binary tree, stored in an array with
one byte per node. Each leaf node represents a heap page, or a lower level
<acronym>FSM</acronym> page. In each non-leaf node, the higher of its children's
values is stored. The maximum value in the leaf nodes is therefore stored
at the root.
</para>

<para>
See <filename>src/backend/storage/freespace/README</filename> for more details on
how the <acronym>FSM</acronym> is structured, and how it's updated and searched.
The <xref linkend="pgfreespacemap"/> module
can be used to examine the information stored in free space maps.
</para>

</sect1>

<sect1 id="storage-vm">

<title>Visibility Map</title>

<indexterm>
 <primary>Visibility Map</primary>
</indexterm>
<indexterm><primary>VM</primary><see>Visibility Map</see></indexterm>

<para>
Each heap relation has a Visibility Map
(VM) to keep track of which pages contain only tuples that are known to be
visible to all active transactions; it also keeps track of which pages contain
only frozen tuples.  It's stored
alongside the main relation data in a separate relation fork, named after the
filenode number of the relation, plus a <literal>_vm</literal> suffix. For example,
if the filenode of a relation is 12345, the VM is stored in a file called
<filename>12345_vm</filename>, in the same directory as the main relation file.
Note that indexes do not have VMs.
</para>

<para>
The visibility map stores two bits per heap page.  The first bit, if set,
indicates that the page is all-visible, or in other words that the page does
not contain any tuples that need to be vacuumed.
This information can also be used
by <link linkend="indexes-index-only-scans"><firstterm>index-only
scans</firstterm></link> to answer queries using only the index tuple.
The second bit, if set, means that all tuples on the page have been frozen.
That means that even an anti-wraparound vacuum need not revisit the page.
</para>

<para>
The map is conservative in the sense that we make sure that whenever a bit is
set, we know the condition is true, but if a bit is not set, it might or
might not be true. Visibility map bits are only set by vacuum, but are
cleared by any data-modifying operations on a page.
</para>

<para>
The <xref linkend="pgvisibility"/> module can be used to examine the
information stored in the visibility map.
</para>

</sect1>

<sect1 id="storage-init">

<title>The Initialization Fork</title>

<indexterm>
 <primary>Initialization Fork</primary>
</indexterm>

<para>
Each unlogged table, and each index on an unlogged table, has an initialization
fork.  The initialization fork is an empty table or index of the appropriate
type.  When an unlogged table must be reset to empty due to a crash, the
initialization fork is copied over the main fork, and any other forks are
erased (they will be recreated automatically as needed).
</para>

</sect1>

<sect1 id="storage-page-layout">

<title>Database Page Layout</title>

<para>
This section provides an overview of the page format used within
<productname>PostgreSQL</productname>