A Memory-efficient Store for SILT: Part II

Learn how to design a memory-efficient key-value store.

Compact recursive representation

Trees are generally implemented using pointers. Pointers are required in nodes to store the address of their child nodes. Based on the size and architecture of the underlying hardware, these pointers may be up to eight bytes long. Every internal node will need at least one pointer—this means it isn’t memory-efficient.

We will represent our tries without using pointers. Our representation will essentially be a string containing our compact representation of the prefix tree. This is a recursive representation, meaning we can capture it using a recursive function. The below representation is for our memory-efficient store's in-memory index prefix tree TT with left subtrie LL and right subtrie RR:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.