This repository was archived by the owner on Oct 20, 2024. It is now read-only.
Reuse unused space in values when values are deleted and updated out-of-place #1
Description
When an entry is moved or deleted from the values file, the occupied space for the entry is just left over and not reused. We could keep a track of regions in the values file after moving or deleting entries, then reuse them when inserting/moving entries.
The data structure we use to store this information must be compact, efficient and fast (for insertion, deletion and lookups). A skip list could be a good choice, but I haven't really given a thought to this. We could also consider using a B+Tree.