[cmckn]

Well, any hot table should be indexed (with regards to your access patterns) and, thankfully, the data structures used to implement tables and indexes don't behave linearly :)

Of course, if your application rarely makes use of older rows, it could still make sense to offload them to some kind of colder, cheaper storage.