Support Fixed sized keys and values

[tomijaga]

Memory BTree

Currently, we only support dynamic keys and values and because the sizes are arbitrary we have to store the sizes for each key pair. We store an extra 2 bytes for each key and an extra 4 bytes for each value. In addition to these we also store a pointer to each key and value in the leafs so their data can be updated without having to resize the leaf.

In this issue we want to optimize the storage for fixed-sized keys and values.

Fixed-size data means every instance in the collection has exactly the same size, defined at initialization. For example, a Nat64 type represented by an 8-byte Blob is fixed-size.

Important: This differs from max-size data, where values can be smaller than the maximum. Max-size data still requires size storage to prevent undefined value returns.

Planned changes

• Remove the extra 2 byte key size and 4 byte value size for fixed size variables.
• Replace the value pointer with the actual value if its fixes size is <= 8. To maintain backward compatibility even if the value is less than 8 bytes, we will always allocate 8 bytes for the value.
  • Unfortunately, we can't do the same for key pointer because of the way our key-value pairs are stored internally

Leaf structure

• current

 Leaf [ 0 .. n key-pair pointers ] 
   └─› key pair pointer [ key, key_size, value_size, value pointer ] 
         └─› value pointer [value]

• new structure

 Leaf [ 0 .. n key-pair pointers ] 
   └─›  key pair pointer [ key, value ]

why is this change needed?

• saves memory for fixed for fixed sized keys and values.
• a memory btree that has a variable key (Text) and a fixed sized value (Nat32) can save 12 bytes (4 byte size and 8 byte pointer) for each entry