A Memory-efficient Store for SILT: Part II
Learn how to design a memory-efficient key-value store.
We'll cover the following
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
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.