Suppose there are ~10,000's of keys, where each key corresponds to a stream of events. I'd like to support the following operations:

• push(key, timestamp, event) - pushes event to the event queue for key, marked with the given timestamp. It is guaranteed that event timestamps for a particular key are pushed in sorted or almost sorted order.
• tail(key, timestamp) - get all events for key since the given timestamp. Usually the timestamp requests for a given key are almost monotonically increasing, almost synchronously with pushes for the same key.

This stuff has to be persistent (although it is not absolutely necessary to persist pushes immediately and to keep tails with pushes strictly in sync), so I'm going to use some kind of database.

What is the optimal kind of database structure for this task? Would it be better to use a relational database, a key-value storage, or something else?