Compaction without full LSM

I thought about a bit on how to implement basic compaction (which is needed as soon as you can delete data), without going full LSM-style. Here's an idea how it could be done.

### Data structures needed

Add a MemTable where the data is inserted first, before it's flushed to disk. This is probably a good idea independent of the compaction (though we'll need this later for the compaction). For the compaction, you'd need to know which parts of the append-only primary storage file are not in use anymore. For this, I propose using a persisted append-only B-tree, that keeps tracks of the deletes. It will only contain keys and no values. The keys are the offsets of the the primary storage file of the data items that were deleted.

### The compaction process

When you perform a compaction, the first step is to stop writing to the primary file. All inserts from now on are only stored in the MemTable. Now you start scanning through the primary storage file and write it into a new file. In parallel you traverse the B-tree that contains all deletes. As the B-tree has the offsets sorted, you can easily determine whether you skip over a data item (that was deleted) or not.

In case you had an index on the original file for faster access (you usually would have one), you rebuild one from scratch for the new file. Once done, flip over to the new file as primary storage and start letting the MemTable flush to the file again. Now you can delete the old file and index.

### Details about the data structures

#### MemTable

As the MemTable will be the only storage while the compaction in happening, you probably want to combine it with a write-ahead-log (WAL), where you just store all the inserts and deletes sequentially as they came in. This way you can replay things into the database in case of a crash. There are lots of details that need to be considered, e.g. making sure you know where to start the replay in case of a crash. For this you'll likely need something like sequence numbers. Another good idea is to make the operations on the primary storage idempotent, so you might waste some IO, but at least won't get into an inconsistent/wrong state.

#### B-tree

The append-only B-tree can use fixed node sizes (I'd use 4KiB) to make it usable with direct access (DMA). The structure I have in mind is having a 8 byte prefix for each node, the rest filled with data, which is padded with zeros up to the full 4KiB. The node prefix consists of:

```rust
#[repr(u8)]
enum NodeKind {
// Root node.
Root = 0,
// Inner node that contains links to its children.
Inner = 1,
// Leaf node which contains the actual values.
Leaf = 2,
}

struct NodePrefix {
/// Kind of the node (8-bit value).
kind: NodeKind,
/// The version the b-tree has.
version: u8,
/// The actual data length that is contained in the block.
///
/// The block is fixed sized, so the actual data might be smaller than this. The length is
/// without this prefix, so the minimum number is 0.
len: u16,
}
```

The main distinction is between inner and leaf nodes:

- Leaf nodes: Their data is just a list of 64-bit values which are offsets in the primary storage file (they point to the data items that were deleted).
- Inner nodes: They have 2-tuples with `(key, value)`, where the key is one of those 64-bit offsets to the primary storage (it's always the highest key of the child node it points to), and a pointer to the child node (that pointer is within the persisted B-tree itself).
- Root nodes: They are the same as inner nodes. The reason to make the special is to be able to find the root node within the persisted file. You won't need a head/footer. You can just scan the file from the back and look at every 4KiB boundary. If the first byte is `0x00`, then you know you are at the most current root node. Even if something went wrong while writing the tree and you have garbage at the end, you would just skip over it and still find the most recent root.

The whole B-tree building, with splitting nodes etc. is the same as in every B-tree. The only difference in an append-only B-tree is, that you need to write the whole path from the insertion up to the root. Also no rebalancing will be performed. It is expected that the tree won't grow too large, as it is emptied after each compaction anyway.

As we use the B-tree for keeping track of deletions in the primary storage, we don't need to have a `delete()` operation. We never undo any deletes. If something with the same key gets added again to the primary storage, it will be appended and hence get a new position. You'd still want to delete the data at the previous position it was stored at.

In a content-addressed system it might make sense to have a way to undo deletes, as the values will always be the same. Though this makes things a lot more complicated and might not be worth the trade-offs. I'd consider this an optimization that highly depends on your use case/access patterns and would need to be benchmarked properly.