A Memory-efficient Store for SILT: Part II

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 $T$ with left subtrie $L$ and right subtrie $R$: