You are more or less on the right track. In your approach B, it is strictly better to keep the values in the primary key index, so you don’t have to follow a level of indirection.
(‘pk’, key1) := (val1, 2018-05-01)
…
(‘exp’, 2018-05-01, key1) := ()
Approach B is asymptotically optimal, since you only do O(1) work for each update to a key. But there are imaginable workloads where approach A would be faster in practice.
Dave