By "immediately higher and immediately lower keys/indexes" I infer you mean the nearest existing keys present in the array, not ($key-1, $key+1) regardless of whether present. Correct?

I do like your approach; using a hash for the actual storage (i.e. values) is sane enough. For the index management, I would look at Set::IntSpan::Fast. Here's the basic idea: use this module to remember the ranges (IntSpan's) of the indices absent from the hash, i.e. the complement of the set of indices present in the hash. (Don't worry about the unbounded ranges at the upper and lower ends; Set::IntSpan::Fast handles them just fine.) Handling a "miss" and getting the nearest keys will be fairly straightforward, though the API doesn't include a method specifically for that so you'll have to code it up yourself. Take a look at the source, particularly the _find_pos and _iterate_ranges internal functions. Note in particular that _find_pos does the binary search you need. :-)