Key trimming after removing a key from index
- Dominant language
- Go
- Stars
- 14
- Forks
- 2
- PR merge metrics
- No merged PRs in 30d
Description
Extends: #5
After removing a key from the index, if we want to optimize for storage we need to reorganize keys.
We only save a few bytes per removal, and only in certain cases, but it may be worth if we are storing a large amount of data (it may have limited impact for the MVP):
```
// Trim example
3 4 5 3 4 5 3 4 5 3 4 5
3 4 6 6 3 4 6 6 3 4 6 6 3 4 6 6
3 4 6 8 (remove) --> 3 4 6 9 1 3 (remove) --> 3 4 6 9 2 4 (can trim?) --> 3 4 6 9 (trimmed)
3 4 6 9 1 3 3 4 6 9 2 4
3 4 6 9 2 4
// No trim example
3 4 5 3 4 5 3 4 5 3 4 5
3 4 6 6 3 4 6 6 3 4 6 6 3 4 6 6
3 4 6 8 (remove) --> 3 4 6 9 1 3 (remove) --> 3 4 6 9 2 4 (can trim?) --> 3 4 6 9 2 4 (nope..)
3 4 6 9 1 3 3 4 6 9 2 4 3 4 6 9 2 5 3 4 6 9 2 5
3 4 6 9 2 4 3 4 6 9 2 5
3 4 6 9 2 5
```
In each removal a single key is eligible to be trimmed, the one that occupies the place of the removed key. The algorithm to trim is the following:
- Check the largest common prefix of the replacing key with the previous key and the following one.
- If len(common_prefix_prev) > len(common_prefix_next) --> Can be trimmed
- Else --> do not trim.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.