Tables and Row Storage

A database table is a set of rows. In memory, each row is a struct — an ordered collection of typed values. A table is an array of rows, with a fixed schema (column names and types).

Real databases store rows in pages on disk (SQLite uses 4 KB pages), but we'll start simpler: one flat file per table, with rows serialized end-to-end. The challenge is not the disk format — it's managing a growing array without knowing how many rows you'll need.

Why an Array? (And Not a Linked List)

The obvious alternative to a growing array is a linked list: every insert mallocs one node, no reallocation ever, O(1) append. Databases almost never do this, and the reason is the memory hierarchy.

Your CPU doesn't read memory one byte at a time — it reads cache lines (64 bytes on x86). When you touch rows[0], the CPU pulls in the surrounding bytes for free, and its prefetcher notices the sequential pattern and starts loading rows[1], rows[2], ... before you ask. Scanning a contiguous array runs at close to memory bandwidth. A linked list defeats all of this: each node lives at an unpredictable address, so every node->next is a potential cache miss — a stall of ~100ns while the CPU waits for DRAM. A full-table scan over a linked list can easily be 10–50× slower than the same scan over an array, for identical big-O.

This exact logic scales up one level in the hierarchy: what cache lines are to RAM, pages are to disk. A disk read fetches 4 KB whether you wanted 4 bytes or all of them, so databases pack rows contiguously into pages for the same reason we pack them contiguously into an array. Learn the pattern once here and you'll recognize it everywhere in storage engines.

Why Track Capacity Separately From Count?

You've seen two strategies for a growing collection:

• Preallocate and return an error when full (simple, wastes space, and the first user with row n+1 files a bug report).
• Dynamic reallocation (malloc a bigger array, copy old data, free old space).

Databases use the second. The key design decision is that the table tracks capacity (how much space is allocated) separately from count (how much is used). A table with 3 rows might have capacity for 8, so the next 5 inserts are just a struct copy — no allocator call, no copying the whole table. The allocator is only involved on the rare insert that crosses the capacity boundary. This idea — reserve more than you need so the common case is cheap — shows up all over systems code: file systems preallocate extents, Postgres leaves free space in pages for updates, Go slices and C++ vectors work exactly like this.

Growth Strategy: Why Double?

When you run out of space, how much space do you allocate next? Allocating just count + 1 means every insert triggers a reallocation — and each reallocation copies every existing row, so inserting n rows costs 1 + 2 + 3 + ... + n copies: O(n²) total. For a million rows that's half a trillion copies. Doubling the capacity (new_capacity = capacity * 2) means you reallocate only log₂(n) times, making the total cost O(n) — linear, which is optimal. This is the amortized analysis of dynamic arrays: individual inserts are occasionally expensive, but the average cost per insert is constant.

The math: if you start with capacity 1 and double each time, after k reallocations you have capacity 2^k. To store n items, you need 2^k ≥ n, so k = log₂(n). Each reallocation i costs 2^i work (copying 2^i items). Total:

∑(2^i for i = 0 to log₂(n)) = 2^(log₂(n)+1) - 1 = 2n - 1 = O(n)

Any constant factor works (1.5×, 1.75×), but the tradeoff is real: a larger factor means fewer reallocations but more wasted memory (2× can leave the array half empty), a smaller factor is thriftier with memory but reallocates more often. Some allocators prefer 1.5× because the freed old blocks can eventually be reused for a future growth — with 2×, the sum of all previous allocations is always slightly smaller than the next one, so old space never fits. For this course, 2× is fine.

Why Fixed-Size Rows (For Now)

Our schema is hardcoded and every row is exactly the same size. That's a real simplification — text columns in real databases are variable-length — but it buys us two properties that make everything else in this course tractable:

1. Row i lives at a computable address: rows + i * sizeof(Person). No per-row bookkeeping, no offset table.
2. Serialization is trivial: the in-memory array is the disk format (lesson 2).

Real engines pay significant complexity for variable-length rows: SQLite encodes each row as a varint-prefixed record and keeps a cell pointer array in every page; Postgres has a line-pointer array plus TOAST for oversized values. The concepts you build here — capacity management, serialization, indexing — carry over unchanged; only the byte-level encoding gets harder.

Schema and Row Types

For this course, we'll use a fixed schema: a row is always a struct with the same columns. (Real databases read schema from a catalog table — in SQLite, sqlite_schema is itself an ordinary table that stores the CREATE TABLE statements; we hardcode ours for simplicity.) Let's define a Person row: an auto-increment ID, a name, and an age.

#include <stdint.h>

typedef struct {
    uint32_t id;        /* auto-increment primary key */
    char name[256];     /* NUL-terminated string */
    uint32_t age;       /* unsigned integer */
} Person;

Note the fixed-width types: uint32_t, not int or long. Databases care about exact sizes because these bytes will eventually hit disk (lesson 2), and long is 4 bytes on some platforms and 8 on others. Also note the layout: 4 + 256 + 4 = 264 bytes, and since the largest field alignment is 4, the compiler inserts no padding. That's deliberate — padding bytes are uninitialized garbage, and in lesson 2 we'll write these structs to disk verbatim. If you ever reorder fields or add a uint8_t, check the layout again.

A table holds a growing array of these:

typedef struct {
    Person *rows;       /* dynamically allocated array */
    uint32_t count;     /* number of rows in use */
    uint32_t capacity;  /* how many rows we have space for */
    uint32_t next_id;   /* the ID to assign to the next insert */
} Table;

next_id is a monotonic counter: it only ever goes up, even when rows are deleted. We'll see why ID reuse is dangerous in the update/delete lesson.

When you insert a row, you:

1. Check if count >= capacity. If so, realloc to a bigger capacity (e.g., capacity * 2, or 16 if capacity was 0).
2. Set rows[count].id = next_id++ and copy in the name and age.
3. Increment count.

One C-specific trap in step 2: copy the name with a bounded copy (strncpy up to 255 bytes) and explicitly NUL-terminate. strncpy does not write a terminator when the source fills the buffer — forgetting this is a classic buffer over-read waiting to happen, and databases are exactly the kind of long-lived process where it eventually does.