Hierarchical, ordered, key-value store?

Question

I'm looking for a database system which has the following capabilities:

1. Hierarchical (multi-dimensional) keys
2. An ordering of keys at each dimension

So if my key is like App > User > Item I can run a query like: "what is the next item for this user?" Or "What is the next user for this app?"

I basically want a multi-dimensional tree. I found GTM, and am wondering if there are any other products like this.

Answer 1

Given your requirements I'd say that using multiple nested b-trees is a good solution.

You may also want to consider using a single b-tree and some clever key encoding so that for each segment in the key (path) there is a reserved min-token and max-token.

Having such a key would allow you to use standard b-tree access methods for your queries.

"what is the next item for this user" would be: find the key greater than App > User > Item > **MAX**

and, "what is the next user for this app" would be: find the key greater than App > User > **MAX**

For the second approach (key encoding instead of nested trees) any b-tree based No-SQL solution would suffice. Which one to choose depends on you programming environment and other requirements you might have.

Answer 2

I've come across this problem before; I used a column called parent_id which used the id of, well, the parent to link the children. In a simple example, we set the id to 5 for the dimension "Item". Therefore every row with a parent_id of 5 will come under "Item". You can then use a foreach to link all the parents up.