1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<HTML
><HEAD
><TITLE
>Free Space Map</TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.79"><LINK
REV="MADE"
HREF="mailto:pgsql-docs@postgresql.org"><LINK
REL="HOME"
TITLE="PostgreSQL 9.1.15 Documentation"
HREF="index.html"><LINK
REL="UP"
TITLE="Database Physical Storage"
HREF="storage.html"><LINK
REL="PREVIOUS"
TITLE="TOAST"
HREF="storage-toast.html"><LINK
REL="NEXT"
TITLE="Visibility Map"
HREF="storage-vm.html"><LINK
REL="STYLESHEET"
TYPE="text/css"
HREF="stylesheet.css"><META
HTTP-EQUIV="Content-Type"
CONTENT="text/html; charset=ISO-8859-1"><META
NAME="creation"
CONTENT="2015-02-02T21:03:01"></HEAD
><BODY
CLASS="SECT1"
><DIV
CLASS="NAVHEADER"
><TABLE
SUMMARY="Header navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TH
COLSPAN="5"
ALIGN="center"
VALIGN="bottom"
><A
HREF="index.html"
>PostgreSQL 9.1.15 Documentation</A
></TH
></TR
><TR
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="top"
><A
TITLE="TOAST"
HREF="storage-toast.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="top"
><A
HREF="storage.html"
ACCESSKEY="U"
>Up</A
></TD
><TD
WIDTH="60%"
ALIGN="center"
VALIGN="bottom"
>Chapter 55. Database Physical Storage</TD
><TD
WIDTH="20%"
ALIGN="right"
VALIGN="top"
><A
TITLE="Visibility Map"
HREF="storage-vm.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
></TABLE
><HR
ALIGN="LEFT"
WIDTH="100%"></DIV
><DIV
CLASS="SECT1"
><H1
CLASS="SECT1"
><A
NAME="STORAGE-FSM"
>55.3. Free Space Map</A
></H1
><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 <TT
CLASS="LITERAL"
>_fsm</TT
> suffix. For example,
if the filenode of a relation is 12345, the FSM is stored in a file called
<TT
CLASS="FILENAME"
>12345_fsm</TT
>, 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 <TT
CLASS="FILENAME"
>src/backend/storage/freespace/README</TT
> for more details on
how the <ACRONYM
CLASS="ACRONYM"
>FSM</ACRONYM
> is structured, and how it's updated and searched.
The <A
HREF="pgfreespacemap.html"
>pg_freespacemap</A
> module
can be used to examine the information stored in free space maps.</P
></DIV
><DIV
CLASS="NAVFOOTER"
><HR
ALIGN="LEFT"
WIDTH="100%"><TABLE
SUMMARY="Footer navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
><A
HREF="storage-toast.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="index.html"
ACCESSKEY="H"
>Home</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
><A
HREF="storage-vm.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>TOAST</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="storage.html"
ACCESSKEY="U"
>Up</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>Visibility Map</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>
|
