Implementing a cache

[qznc via Digitalmars-d-learn]

I want to implement some caching for HTTP GET requests. Basically 
a map of URL to content. A cache needs some additional meta data 
(size, age, etc).

There seem to be two basic data structures available: Associative 
array (AA) or red black tree (RBT).

With AA cache eviction is inefficient. It requires to sort the 
keys of the AA with respect to a field in the value. Stack 
overflow says "use RBT instead" [0].

With RBT retrieving something is inefficient. To get an entry, we 
need to create an fake entry with the key and get a range of 
entries 'equal' to the fake one? Or can I exploit some "find on 
sorted range" algorithm somewhere?

Alternatively, any better idea to implement the cache? I guess 
there is no off-the-shelf/dub solution.

[0] 
https://stackoverflow.com/questions/10060625/how-to-sort-associative-arrays