Closed
Description
Snapshot is always created and processed in order, taking advantage of that, we can apply delta encodings to some fields:
- version
IAVL tree has the nice property that parent node's version is always bigger than or equal to children's version, and in snapshot, nodes are added in post-order, where parent node is put after children nodes, so we can only record the delta value, to be specificparent version - max(left version, right version), smaller value results in smaller encoded size with varint encoding. - key
After the export: don't export branch node's key in snapshot #688 improvement, we only have leaf keys in snapshot, they are ordered, so delta encoding can also potentially have some good compression rate there. - height
since IAVL tree has the invariant thatparent height = max(left height, right height) + 1, I think we don't need to encode the height field at all in the snapshot.
The version and height compression rely on the fact that nodes are exported in post-order. the key compression only need the leaf nodes are exported in order.
Metadata
Metadata
Assignees
Labels
No labels