# What is a fully persistent B-tree?

> A fully persistent B-tree keeps every version readable and lets any version start a new one. What the term means, and what it buys a database.

Source: https://stolondb.com/blog/fully-persistent-b-tree/ · Page title: What is a fully persistent B-tree? — Stolon

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)](https://www.cs.cmu.edu/~sleator/papers/another-persistence.pdf). 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](https://stolondb.com/guides/history/)).

## 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.

- [How it works](https://stolondb.com/how-it-works/) — The engine, branches, merge, durability and measurements.
- [Read and restore a past moment](https://stolondb.com/guides/history/) — Use any version as a starting point.