Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

compress radix trees #79

Open
dvc94ch opened this issue Oct 28, 2021 · 2 comments
Open

compress radix trees #79

dvc94ch opened this issue Oct 28, 2021 · 2 comments
Assignees
@rklaehn

Comments

@dvc94ch
Copy link
Contributor

dvc94ch commented Oct 28, 2021

No description provided.

@dvc94ch dvc94ch changed the title research/design better db backend compress radix trees Oct 29, 2021
@rklaehn
Copy link
Contributor

rklaehn commented Nov 9, 2021

It is good that this is not marked with m1, since this deserves some thought.

One thought I had is that typically the need for compression is largest for the leafs. For the branches, there is already common prefix elimination due to the structure of the radix tree. So maybe just compress the leafs. But this will be difficult to do while having the ArchivedRadixTree still being useful.

@rklaehn
Copy link
Contributor

rklaehn commented Nov 9, 2021 •
edited
Loading

Might be worth looking into lz4. It is basically 1/2 of a typical compression algo - just does the dedup stage, not the entropy coding / huffman stage. It is very fast, and there is a rust native version. Might be good enough.

https://crates.io/crates/lz4_flex

Also by Yann Collet, just like zstd.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@rklaehn rklaehn

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@rklaehn @dvc94ch