Chunked LPM Tree

[GeorgyKirichenko]

Motivation
LPM tree is not truly dynamically extensible.
During LPM tree initialization the tree assumes some capacity value large enough to accommodate all the values and allocates continuous block of memory to fit all chunks inside.
The in case of space underestimation the tree doubles the space and tries to reinsert all incoming values again, and so on, until all values would fit into.
Any internal chunk is addressable by an identifier which is effectively an offset of the chunk inside allocated memory.

Suggested design
Two level chunk addressation: consider the chunk identifier as an extent identifier and index of the chunk inside the extent.
This means that we can dynamically allocate an extent and attach them to a LPM tree. However this requires for an additional index array storing an extent address by it's identifier.

Considerations about the extent index size:
Now we have 24 bits for both value and chunk identifier stored in a 4-byte value, then if an extent contains 2^C chunks we will have

• each chunk is 256 * 4 bytes in size
• each extent is 2^C * 256 * 4 bytes in size
• 2^{24-C} * 8 bytes for extent index

For an example if we choose C=10 then the resulting values will be equal

• 1MiB for each extent
• 128Kib for the extent index