I'm now facing a problem in real life involving efficient data structures (yay!): I need a data structure for storing key-value data and supports prefix-based searching and, considering N the amount of keys and M a key length, inserting and deleting in O(M). The data structure will be used in an embedded software, so it must be memory efficient.

My current solution is using a trie, but the memory overhead is too big for the application. It's an straight-forward trie implementation, but splitting strings in nibbles instead of bytes. Tips on improving the memory usage for the trie are welcome.

Any thoughts?