What is a fully persistent B-tree?
A B-tree in which every version stays readable and any version can start a new one, so its versions form a tree. Stolon is built on one, which is why a branch copies nothing and reads stay flat as branches get deeper and more numerous.
The definition
The terms come from the data-structures literature, starting with Driscoll, Sarnak, Sleator and Tarjan (1989). A structure is persistent when a change makes a new version and leaves the old one readable. What differs is which versions can change:
| Readable | Changeable | History is | |
|---|---|---|---|
| Ephemeral | the current version | the current version | not kept |
| Partially persistent | every version | the newest | a line |
| Fully persistent | every version | any version | a tree |
| Confluent | every version | any version, and two can be combined into one | a graph |
What it buys a database
- Branching copies no data. Each branch added 489 bytes and no data pages.
- Branch count and depth leave read cost unchanged. Reads are flat across 125 levels of branch depth, and a read scans 2,100 entries and 16 pages at 100, 1,000 and 10,000 live branches.
- Any version is a starting point. Read a table at a past moment, branch from it, compare it with now, or put a branch back to it (the history guide).
Three objections to building one on disk
Each has an answer, and Stolon is built on it.
- Nodes that outgrow a page. Stolon's pages never grow, and large values are stored in chunks.
- Chasing pointers between versions. A read walks from the root to a leaf, as in any B-tree. Nothing follows pointers from version to version.
- Reclaiming space. Dropped branches and expired history are reclaimed automatically, and the file shrinks to about what it still holds, without stalling the database.