ipld / ipld/go-storethehash

Key trimming after removing a key from index

Open
#7 3 comments 0 reactions 0 assignees View on GitHub
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.