• Limitations of Page Class
  1. Linear Scan
     1. Finding space for a new tuple requires a linear scan
     2. Poor handling of variable-length tuples leads to wasted space
  2. Compaction

     1. Periodically, we must compact this fragmented page, moving tuples around to consolidate free spaces

        

1. Slotted Pages

A Slotted Page is a structure designed to efficiently manage variable-length tuples within a page. It solves limitations of traditional page classes by keeping metadata in a slot array.

Slot Array and Metadata

• Each slot in the slot array contains:
  • Offset: Where the tuple starts within the page.
  • Length: The size of the tuple.

Slot Structure

struct Slot {
    uint16_t offset;  // Start position of the tuple in the page.
    uint16_t length;  // Length of the tuple data.
};

Slotted Page Class

A Slotted Page contains:

• Page Data: Stores actual tuples in a contiguous block of memory.
• Slot Array: Tracks metadata for each tuple.
• Free Space Offset: Keeps track of where the free space begins.

Slotted Page Structure

slots enable direct access to any tuple by index

class SlottedPage {
    std::unique_ptr<char[]> page_data; // Array to store page data.
    std::vector<Slot> slots;          // Slot array for metadata.
    size_t free_space_offset;         // Offset for free space.
};

2. Adding Tuples to a Slotted Page

When adding a tuple:

1. Check if there is enough space.