How about some sort of reverse index? Maybe slice the range into N contiguous sub-ranges and maintain a list of all keys that fall within each sub-range. Then, when you need to find all keys between A and B, look at which sub-ranges intersect the interval (A B), and select keys from them.

This may or may not be feasible for you, depending on your application, but if it is, it could reduce the query time dramatically.

Jim