Tutor Lesson

Try Equal-Sized Records First

Consider a users table containing a unique integeridand a variable-lengthname. CSV delimiters would make direct movement between rows impossible because the file must be scanned byte by byte to locate each separator.

An initial improvement is to assign every column a fixed width. If an ASCII name may contain at most 255 characters, one byte records its actual length because eight bits represent values through 255, while another 255 bytes reserve the character data.

• The integeridoccupies 4 bytes.
• The stored name length occupies 1 byte.
• The reserved name area occupies 255 bytes.
• Each complete record therefore occupies 260 bytes.

To locateid = 50, read a four-byte key and, after a mismatch, move to the next record, 260 bytes from the current record’s start. This linear search costs $O(n)$. It may work for a small file, but repeated disk access makes it unsuitable for a table with many rows.

See Why an Index Is Necessary

A primary-key index reduces lookup to $O(log n)$. A balanced binary search tree could map each key to its row number, allowing the engine to calculate the row's byte position because every record has equal size. However, an ordinary binary tree presents two database problems.

1. Ascending insertions can turn an unbalanced tree into a linked list, restoring the $O(n)$ worst case.
2. A persistent tree may be gigabytes large and unable to fit in RAM, so the engine must retrieve it from disk in pieces.

Insert Keys by Splitting Full Nodes

When the target node is full, its median key moves into the parent and the remaining keys separate into two sibling nodes. A full root has no parent, so the operation first creates a new root. Splits may propagate upward recursively as the tree becomes taller.

Repeating this process keeps the tree dense and balanced rather than allowing it to collapse into a linear chain.

Fit Variable-Length Cells into a Page

Reserving 255 bytes for every short name wastes space. With variable-length records, however, row numbers no longer reveal record positions, and moving large records to preserve sorted order is expensive. A slotted page separates compact offsets from the record contents.

• A slot array grows rightward from the page's beginning. Each entry is a two-byte offset to a record.
• Variable-length cells grow leftward from the page's end.
• The page becomes full when the slot array and cell area meet.

A new cell is placed in the cell area and receives a new slot entry. Binary search operates over the fixed-size slot array. To maintain key order, the engine shifts two-byte slot entries instead of moving all the variable-length record bytes.

Each B-Tree cell also carries a child page number. The keys reached through that pointer fall in the ordered range determined by the cell's key and the preceding key.

Continue Oversized Rows onto Overflow Pages

A row larger than one page, such as a long blog post, must be divided. Once it crosses a chosen threshold—for example, one quarter of the page size—the first chunk remains in the B-Tree cell. The cell's final four bytes point to an overflow page, whose header points to the next overflow page. These pages form a linked list, and reading the row requires joining the chunks again.

Build and Refine the Syntax Tree

1. The tokenizer converts characters into keywords such asSELECTandFROM, along with identifiers, operators, literals, and other token types.
2. The parser turns those tokens into an Abstract Syntax Tree (AST) describing the statement's structure. Top-Down Operator Precedence (TDOP) parsing is one way to build expression trees.
3. The analyzer performs context-dependent checks, including whether a table exists and whether a value has the right type for its column.
4. The optimizer simplifies work that would otherwise be repeatedly evaluated by the interpreter, including constant computations.

Execute an Iterator Plan

The completed AST is compiled into a query-plan tree. Its nodes are iterators that produce tuples, the relational term for rows, one at a time.

• ASequentialScanreads table rows and sends them upward.
• AFiltertests each tuple against a condition.
• AProjectionkeeps the requested columns.

When the root plan needs another tuple, it invokes.next()on its child, which repeats the request down the tree until the scanner advances its cursor. Only the current tuple and cursor state are required, allowing very large tables to flow through the plan without filling RAM.

Sort Data That Exceeds Memory

If all tuples fit in an in-memory buffer, the engine can sort the array directly. Larger results require K-way external merge sort over temporary files.

• During pass 0, load K pages, sort them in memory, and write each sorted run to a temporary file.
• On later passes, merge K runs into a larger run with K input buffers and one output buffer. Every pass expands the run size by a factor of K.

For K = 5, successive passes handle five times more data. Increasing K lowers the number of passes and disk I/O while consuming more RAM. The method can sort terabytes while holding only a small number of pages in memory.