Slotted pages

Deep dive

How it works

In: a page buffer (4-16 KiB) and operations insert(bytes), get(slot), delete(slot), update(slot, bytes) · Out: a record ID (page, slot) or the record bytes · State: header (slot count, upper), slot array of (offset, length), record bytes packed from the page end · Cost: get O(1), insert O(1) plus an occasional O(page) compaction.

0        4                                       upper                   PAGE
+--------+-------+-------+-------+--------------+-------+-------+-------+
| header | slot0 | slot1 | slot2 |  free space  | rec2  | rec1  | rec0  |
+--------+-------+-------+-------+--------------+-------+-------+-------+
 nslots, upper    (off,len) each   ^ lower = 4 + 4·nslots        records grow ←

1. Header: slot count and upper (start of record data). Real pages add the page LSN, a checksum, flags and free-space hints.
2. Insert: needs len bytes plus one slot if no free slot can be reused. If upper − lower is too small but enough dead bytes exist, compact first. Copy the record to upper − len, then write the slot.
3. Delete: mark the slot free. The bytes become garbage until the next compaction.
4. Update: in place if the new value fits. Otherwise move the record inside the page (the slot still points to it), or off the page with a forwarding pointer or a new version (PostgreSQL writes a new tuple).
5. Compact: slide the live records toward the end of the page and rewrite their offsets. Slot numbers stay the same.

Code

pub const PAGE: usize = 4096;
const HDR: usize = 4; // [nslots u16][upper u16]
const SLOT: usize = 4; // [offset u16][len u16]; offset 0 marks a free slot (data never starts at 0)

pub struct Page { buf: Box<[u8; PAGE]> }

impl Page {
    pub fn new() -> Self {
        let mut p = Page { buf: Box::new([0; PAGE]) };
        p.set(2, PAGE as u16);
        p
    }
    fn u16_at(&self, at: usize) -> u16 { u16::from_le_bytes([self.buf[at], self.buf[at + 1]]) }
    fn set(&mut self, at: usize, v: u16) { self.buf[at..at + 2].copy_from_slice(&v.to_le_bytes()); }
    fn nslots(&self) -> usize { self.u16_at(0) as usize }
    fn upper(&self) -> usize { self.u16_at(2) as usize }
    fn slot(&self, i: usize) -> (usize, usize) {
        let a = HDR + i * SLOT;
        (self.u16_at(a) as usize, self.u16_at(a + 2) as usize)
    }
    fn set_slot(&mut self, i: usize, off: usize, len: usize) {
        let a = HDR + i * SLOT;
        self.set(a, off as u16);
        self.set(a + 2, len as u16);
    }
    pub fn free_space(&self) -> usize { self.upper() - (HDR + self.nslots() * SLOT) }

    /// Returns the slot number (stable record ID within the page), or None if it cannot fit.
    pub fn insert(&mut self, rec: &[u8]) -> Option<u16> {
        let n = self.nslots();
        let reuse = (0..n).find(|&i| self.slot(i).0 == 0);
        let need = rec.len() + if reuse.is_some() { 0 } else { SLOT };
        if need > self.free_space() {
            self.compact(); // reclaim bytes of deleted records
            if need > self.free_space() { return None; }
        }
        let i = reuse.unwrap_or(n);
        if reuse.is_none() { self.set(0, (n + 1) as u16); }
        let off = self.upper() - rec.len();
        self.buf[off..off + rec.len()].copy_from_slice(rec);
        self.set(2, off as u16);
        self.set_slot(i, off, rec.len());
        Some(i as u16)
    }

    pub fn get(&self, slot: u16) -> Option<&[u8]> {
        let i = slot as usize;
        if i >= self.nslots() { return None; }
        let (off, len) = self.slot(i);
        (off != 0).then(|| &self.buf[off..off + len])
    }

    pub fn delete(&mut self, slot: u16) {
        if (slot as usize) < self.nslots() { self.set_slot(slot as usize, 0, 0); }
    }

    /// Slide live records to the end of the page. Slot numbers do not change.
    pub fn compact(&mut self) {
        let mut live: Vec<(usize, usize, usize)> = (0..self.nslots())
            .filter_map(|i| { let (o, l) = self.slot(i); (o != 0).then_some((o, l, i)) })
            .collect();
        live.sort_unstable_by(|a, b| b.0.cmp(&a.0)); // highest offset first: never overwrite unmoved data
        let mut upper = PAGE;
        for (off, len, i) in live {
            upper -= len;
            self.buf.copy_within(off..off + len, upper);
            self.set_slot(i, upper, len);
        }
        self.set(2, upper as u16);
    }
}

Complexity and constants

• Get by slot: two dependent loads in one page that is already in cache. Order of ns once the page is in the buffer pool.
• Compaction: one memmove of at most a page, order of 100 ns-1 µs for 4-16 KiB. Do it lazily when an insert would fail, not on every delete.
• Space efficiency: with 100-byte rows on 8 KiB pages, PostgreSQL fits about 60 rows (24 B header + 4 B slot + 24 B tuple header per row). Header overhead is a big share for narrow rows.
• 16-bit offsets limit pages to 64 KiB, or 32 KiB with 15-bit fields as in PostgreSQL.

Efficiency

• Cost: a get is two dependent loads in a page already in cache, order of ns once the page is in the buffer pool; compaction is one memmove of at most a page, order of 100 ns-1 µs for 4-16 KiB. Per-row overhead is slot (2-4 B) plus record header (PostgreSQL 23 B, padded to 24); 100-byte rows fit about 60 per 8 KiB page. Bound: I/O and cache footprint (useful bytes per page read).
• Levers:
  • lazy compaction — only when an insert would fail — always
  • fixed-width fields, compact row header — less per-row overhead — narrow rows
  • fill factor below 100 — updates stay on the page (PostgreSQL HOT), no index writes or splits — update-heavy tables
  • free space map — find an insert target without scanning pages — large heaps
  • full-page images in the WAL or a doublewrite buffer — torn-page protection, a large write cost — in-place page updates
• Naive → standard → state of the art:
  • fixed-size slots per record · wasted space for variable rows
  • slot array with lazy compaction · stable IDs, order of ns access
  • columnar layout or append-only/LSM storage · no in-place updates or compaction

Implementation notes

• Alignment: align record starts (PostgreSQL MAXALIGN = 8) so fields can be read in place. Padding costs space.
• B-tree pages: keep the slot array sorted by key and leave the records in arrival order. Binary search runs over slots, and an insert shifts only 2-4-byte slots, never the records. PostgreSQL nbtree and SQLite (cell pointer array) do this. InnoDB instead keeps records in a linked list in key order with a sparse "page directory" of slots, each owning 4-8 records.
• Free space map: track approximate free bytes per page in a separate structure (PostgreSQL FSM, 1 byte per page) so inserts find a page without scanning.
• Fill factor: leave room for in-place updates (PostgreSQL heap fillfactor < 100 enables HOT updates on the same page).
• Torn pages: a page write is not atomic on most devices. Use checksums, plus full-page images in the WAL (PostgreSQL) or a doublewrite buffer (InnoDB).
• Trailing free slots can be trimmed to give space back to the free area.

Pitfalls

• Reusing a slot while an index still references the old record makes the index return the wrong row. PostgreSQL marks slots dead and reuses them only after VACUUM has removed the index entries.
• Compacting a page while another thread holds a pointer into it. Compaction needs an exclusive latch, and pins must not hold raw pointers across it (PostgreSQL requires a "cleanup lock": exclusive with no other pins).
• Records that never fit (> page − header − slot) need an overflow scheme, and the error path must exist.
• Assuming slot order equals physical order. After updates and compaction it doesn't.
• Fragmentation without compaction: inserts fail on pages that still have enough total free bytes.

Variants and alternatives

In production

• Relational databases: PostgreSQL heap and index pages, SQL Server data pages (row-offset array), InnoDB (page directory), Oracle data blocks (row directory).
• Embedded databases: SQLite B-tree pages (cell pointer array); SQLite ships inside phones, browsers and applications.
• No verified use outside page-based storage engines was found; the layout is specific to in-place variable-length records on fixed pages.

Implementations

Sources

• R. Ramakrishnan, J. Gehrke, Database Management Systems, 3rd ed., 2003 (files and record formats).
• G. Graefe, Modern B-Tree Techniques, Foundations and Trends in Databases, 2011. paper
• PostgreSQL documentation, Database Page Layout. docs
• SQLite documentation, Database File Format. docs