Consider moving in memory cache to a `BTreeMap` instead of `HashMap`

[benthecarman]

Right now we use a HashMap for our in memory storage. It may be more efficient to change to a BTreeMap, this way things like scan_prefix are much more efficient. However it has the tradeoff of being O(log(n)) for insertions, we would probably want to bench mark it which may be hard.