Tables and storage

Each table is a B+ tree clustered on its primary key, stored in 8 KiB pages, with rows of one fixed length so a row never moves when it is updated.

A KDBS table is a B+ tree ordered by its primary key. The tree’s leaves hold the rows themselves, so the table and its primary-key index are one structure. Every row in a table has the same size: a value that does not fit in its column’s fixed-size cell is stored in a separate area, and the row keeps a pointer to it. Because a row never grows, an UPDATE never moves a row to another place.

How it works

Pages

All data lives in one growable data file divided into pages of 8192 bytes. A page is found by arithmetic (offset = page_id × 8 KiB), with no lookup table. Page ids are unsigned 32-bit numbers. Each page carries a CRC32C checksum.

Every data page has a min_key: the lowest key the page may ever hold. It is fixed when the page is created and never changes, and no row with a smaller key is ever placed in the page. Because min_key never changes, a reader can skip pages by key range without taking a lock.

The clustered B+ tree

  (illustration)
                      ┌───────────────┐
                      │  internal     │   separators route a key
                      │  node (root)  │   to the leaf that may hold it
                      └──┬─────────┬──┘
              ┌──────────┘         └──────────┐
      ┌───────▼────────┐             ┌────────▼───────┐
      │ leaf           │ next_page ▶ │ leaf           │
      │ min_key = 1    │             │ min_key = 4096 │
      │ rows 1, 2, ... │             │ rows 4096, ... │
      └────────────────┘             └────────────────┘
        rows sorted by key inside every leaf

A leaf is a data page. It has a slot directory and full rows, each with its multiversion (MVCC) header. The tree is a directory over the data pages, not a second copy of the data.
Rows inside a leaf are sorted by key. A new row takes the slot its key sorts to, whatever order keys arrive in. So the whole table is always in key order, and ORDER BY <primary key> costs nothing.
A key lookup is exact. The descent lands on the one leaf that can hold the key. If the row is not there, it does not exist, and no scan follows.
Two ways to grow a leaf. A key above every key in a full leaf starts a new leaf on the right and moves nothing. This is the usual case for engine-issued keys, which ascend. A key that sorts inside a full leaf splits it: the upper part moves to a new leaf, and the old leaf keeps its min_key.
A split is one log record. Every page a split writes is logged together, so after a crash the split is replayed whole or not at all.

Fixed-length rows

Every row in a table has the same length, fixed by the schema. Fixed-width types use their natural width. Each variable-width value, such as varchar, takes exactly one tagged cell of a fixed width, whatever it holds:

Tag	Cell content	Meaning
null	zeros	SQL `NULL`
inline	length + bytes + padding	The value fits in the cell
spilled	length + pointer	The bytes are in the var-heap

A bare varchar cell is inline_cell_width bytes wide: 64 by default, set once for the instance when it is created.
varchar(N) makes that column’s cell N bytes wide, with 16 ≤ N ≤ 4096. N is a width, not a maximum length: a value longer than N − 3 bytes is stored in the var-heap instead of being refused.
The var-heap is a separate chain of pages for long values. A value is written once and never changed or moved, so an older snapshot that follows an old pointer always finds the bytes it expects. The var-heap is logged and checksummed like table data.
An UPDATE that makes a value longer only changes the cell’s tag. The row keeps its size and its slot.

You can see the fixed length in SHOW PAGE: every slot of a table has the same length. Page 129 is the root page of the sample airlines table.

kdbs> SHOW PAGE 129
page_id=129
page_type=BTREE_LEAF
page_lsn=7048
min_key=0
nr_slots=3
lower=63
upper=7714
free_space=7651
next_page_id=4294967295
slot[0] offset=8030 length=158 dead=0
slot[1] offset=7872 length=158 dead=0
slot[2] offset=7714 length=158 dead=0

NULL

Columns are NOT NULL unless declared NULL, which is the opposite of standard SQL. A table with nullable columns pays one bitmap byte per 8 nullable columns in each row. A table with none pays nothing. The primary key, index keys and covered columns cannot be NULL.

Deleted rows

DELETE marks a row as deleted. The row’s bytes stay in place for snapshots that started before the delete, and the row keeps its key. Only PURGE removes deleted rows. The space a purge frees in a leaf is reused when the leaf next fills.

Example

CREATE TABLE notes (id int64, title varchar(32), body varchar, score int32 NULL);

kdbs> DESCRIBE notes
oid=4027 root_page_id=145 clustered_type=BTREE next_id=1 columns=4 ids_issued=0 ids_remaining=281474976710655 budget_used=0.000% height=1 leaves=1
pos=0 name=id type=int64 notnull=yes pk=yes autoincrement=if-omitted
pos=1 name=title type=varchar(32) notnull=yes pk=no autoincrement=no cabin=auto
pos=2 name=body type=varchar notnull=yes pk=no autoincrement=no cabin=auto
pos=3 name=score type=int32 notnull=no pk=no autoincrement=no cabin=auto

clustered_type=BTREE is the storage form, height and leaves describe the tree, and root_page_id is the page you can pass to SHOW PAGE.

What it guarantees

A row never moves because of an UPDATE. The new version is written in the same page and slot. A split or a placement in the middle of a leaf can still move rows within or between leaves; every structure that remembers a location re-checks it.
Rows are always in key order on every leaf, at any number of cores.
A row whose length does not match its table is treated as corruption, never read.
Long values do not change after they are written. Old versions keep reading the bytes they pointed to.

What it costs

Padding. A short value still uses its whole cell. Choose varchar(N) so that common values fit inline.

The column set is fixed. ALTER TABLE ... ADD COLUMN, DROP COLUMN and type changes are refused, because the row size is a schema constant. Widening a varchar(N) is refused too. Renames are allowed.

kdbs> ALTER TABLE passengers ADD COLUMN x int64
                             ^
ERR NOT_IMPLEMENTED retryable=0 ALTER TABLE ADD is not supported (byte 23); v1 is catalog-only - RENAME TO and RENAME COLUMN - because a relation's row size is a schema constant (invariant 13), so changing the column set is a relation rewrite, not a catalog edit

Values have a size limit. A value larger than one var-heap page (8144 bytes) is refused.
Replaced long values use space until purge. A spilled value that an UPDATE replaces is not released when its version dies.
The data file never shrinks. Pages of a dropped table are reused by later tables, but the file does not get smaller.
float is not stored, because no fixed on-disk encoding has been decided. Use decimal(p, s) or an integer type.

Heap tables (suspended)

The engine also has a second storage form, the heap chain: the same pages with no tree over them, growing only at the end. Creating one is refused while the suspension called SUS-1 stands, and BTREE is the default. Heap tables created before the suspension still open, read, write and recover as before.

kdbs> CREATE TABLE notes (id int64, title varchar(32), body varchar, score int32 NULL) HEAP
                                                                                       ^
ERR HEAP storage is suspended (SUS-1) and no new heap relation is created (byte 81); BTREE is the default and every existing heap relation still mounts and serves. The suspension, its rulings and the condition that lifts it are instructions/v3.0.0/workorder-as-sus1-heap-suspended.md

BTREE and EXPLICIT are still accepted after the column list and change nothing.

How to observe it

Command	Shows
`DESCRIBE <table>`	Storage form, root page, tree height, leaf count, key mark
`SHOW PAGE <id> [VALUES]`	One page’s header (type, `min_key`, free space, `page_lsn`) and slots; `VALUES` dumps the row bytes
`SHOW META`	Page allocation and reuse counters (`pages_allocated`, `pages_freed`, `pages_reused`) and buffer pool counters

Limitations

The buffer pool has a fixed size. buffer_pool_frames is required and is a hard ceiling. When the pool is full, a statement is refused instead of the pool growing.
inline_cell_width is fixed when the instance is created. It is written into the data file and checked at every start; changing it means rebuilding the data.
No VACUUM. Nothing moves live rows to compact a table.