Moved the Store interface to a real key/value store

I was planning to use something like that to find common prefixes but it won't be necessary so I'll remove it.