Module edit 

Changing one key of a built tree without building it again.

A node covers the keys between two keys taller than it. Changing one key rewrites exactly the nodes whose range holds that key: one per layer, from the root down. Below the key’s own layer, an insert splits each of those nodes in two around the key, and a remove joins the two nodes either side of it. Every other node is left where it is, shared with the tree before.

Nothing here is written into the tree until the edit is done. An edit reads the nodes it needs, stores the ones it writes beside the tree, and then applies both at once, so a node it writes and then replaces again never reaches the tree at all.

Structs

Edit 🔒

An edit in progress: the tree as it was, and what the edit has done.

Open 🔒

A node with its keys written out whole, which is how an edit works on it.

Rewritten

The blocks an edit added and took away.

Staged 🔒

A finished edit, ready to be written into the tree.