The Microsoft® SQL Server™ data structures that track free space have a relatively simple structure. This has two benefits:
This increases speed by reducing the amount of disk reads necessary to retrieve allocation information, and increasing the chance the allocation pages will remain in memory, eliminating even more reads.
Each page allocation or deallocation can be performed quickly, decreasing the contention between concurrent tasks needing to allocate or free pages.
SQL Server uses two types of allocation maps to record the allocation of extents:
GAM pages record what extents have been allocated. Each GAM covers 64,000 extents, or nearly 4 GB of data. The GAM has one bit for each extent in the interval it covers. If the bit is 1, the extent is free; if the bit is 0, the extent is allocated.
SGAM pages record what extents are currently used as mixed extents and have at least one unused page. Each SGAM covers 64,000 extents, or nearly 4 GB of data. The SGAM has one bit for each extent in the interval it covers. If the bit is 1, the extent is being used as a mixed extent and has free pages; if the bit is 0, the extent is not being used as a mixed extent, or it is a mixed extent whose pages are all in use.
Each extent has the following bit patterns set in the GAM and SGAM based on its current use.
| Current use of extent | GAM bit setting | SGAM bit setting |
|---|---|---|
| Free, not in use | 1 | 0 |
| Uniform extent, or full mixed extent | 0 | 0 |
| Mixed extent with free pages | 0 | 1 |
This results in simple extent management algorithms. To allocate a uniform extent, SQL Server searches the GAM for a 1 bit and sets it to 0. To find a mixed extent with free pages, SQL Server searches the SGAM for a 1 bit. To allocate a mixed extent, SQL Server searches the GAM for a 1 bit, sets it to 0, and then also sets the corresponding bit in the SGAM to 1. To free an extent, SQL Server ensures the GAM bit is set to 1 and the SGAM bit is set to 0. The algorithms actually used internally by SQL Server are more sophisticated than what is stated here (SQL Server spreads data evenly around a database), but even the real algorithms are simplified by not having to manage chains of extent allocation information.
Page Free Space (PFS) pages record whether an individual page has been allocated, and the amount of space free on each page. Each PFS page covers 8,000 pages. For each page, the PFS has a bitmap recording whether the page is empty, 1-50% full, 51-80% full, 81-95% full, or 96-100% full.
After an extent has been allocated to an object, then SQL Server uses the PFS pages to record which pages in the extent are allocated or free, and how much free space is available for use. This information is used when SQL Server has to allocate a new page, or when it needs to find a page with free space available to hold a newly inserted row.
A PFS page is the first page after the file header page in a data file (with page number 1). Next comes a GAM (with page number 2) followed by an SGAM (page 3). There is a PFS page each 8,000 pages after the first. There is another GAM each 64,000 extents after the first GAM on page 2, and another SGAM each 64,000 extents after the first SGAM on page 3.