Skip to content
This repository has been 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

Open
itsaky opened this issue Sep 10, 2024 · 0 comments

Comments

@itsaky
Copy link
Member

itsaky commented Sep 10, 2024

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.

@itsaky itsaky changed the title Reuse unused space in values when when values are deleted and inserted Reuse unused space in values when values are deleted and inserted Sep 10, 2024
@itsaky itsaky changed the title Reuse unused space in values when values are deleted and inserted Reuse unused space in values when values are deleted and updated out-of-place Sep 10, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant