If I were to implement it, I would have a custom B+tree where you have a double-layer. The "upper" half of the tree the blocks are sorted by the "key". Once you

If I were to implement it, I would have a custom B+tree where you have a double-layer. The "upper" half of the tree the blocks are sorted by the "key". Once you get to the "leaf" nodes of the upper layer, you have a "lower layer" that contains blocks, all with the same key (or omit it), but sorted by the timestamp/tx instant. You get O(log(n) + log(m)) for historical queries, but O(log(n)) for "current" queries. Or you can just index all modifications to all keys and have them ordered by key then tx, which will give you O(log(n)), but where your n is all values that have ever been set set.