<?xml version="1.0" encoding="UTF-8" standalone="no"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>68.3. Free Space Map</title><link rel="stylesheet" type="text/css" href="stylesheet.css" /><link rev="made" href="pgsql-docs@lists.postgresql.org" /><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><link rel="prev" href="storage-toast.html" title="68.2. TOAST" /><link rel="next" href="storage-vm.html" title="68.4. Visibility Map" /></head><body><div xmlns="http://www.w3.org/TR/xhtml1/transitional" class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">68.3. Free Space Map</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="storage-toast.html" title="68.2. TOAST">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="storage.html" title="Chapter 68. Database Physical Storage">Up</a></td><th width="60%" align="center">Chapter 68. Database Physical Storage</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 11.5 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="storage-vm.html" title="68.4. Visibility Map">Next</a></td></tr></table><hr></hr></div><div class="sect1" id="STORAGE-FSM"><div class="titlepage"><div><div><h2 class="title" style="clear: both">68.3. Free Space Map</h2></div></div></div><a id="id-1.10.20.5.2" class="indexterm"></a><a id="id-1.10.20.5.3" class="indexterm"></a><p> Each heap and index relation, except for hash indexes, has a Free Space Map (FSM) 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 <code class="literal">_fsm</code> suffix. For example, if the filenode of a relation is 12345, the FSM is stored in a file called <code class="filename">12345_fsm</code>, in the same directory as the main relation file. </p><p> The Free Space Map is organized as a tree of <acronym class="acronym">FSM</acronym> pages. The bottom level <acronym class="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. </p><p> Within each <acronym class="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 class="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. </p><p> See <code class="filename">src/backend/storage/freespace/README</code> for more details on how the <acronym class="acronym">FSM</acronym> is structured, and how it's updated and searched. The <a class="xref" href="pgfreespacemap.html" title="F.26. pg_freespacemap">pg_freespacemap</a> module can be used to examine the information stored in free space maps. </p></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="storage-toast.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="storage.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="storage-vm.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">68.2. TOAST </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> 68.4. Visibility Map</td></tr></table></div></body></html>
