Random access to a huge image?

I'm looking for a way to store a huge image in a way that allows random access to small regions without the need to load the whole image into memory. The focus is on speed and on a low memory footprint.

Let's say the image is 50k*50k 32-bit-pixels, amounting to ~9 GB (Currently it is stored as a single tiff file). One thing I found looks quite promising: HDF5 allows me to store and randomly access integer arrays of arbitrary size and dimension. I could put my image's pixels into such a database.

What (other) (simpler?) methods for efficient random pixel access are out there?

I would really like to store the image as a whole and avoid creating tiles for several reasons: The requested image region dimensions are not constant/predictable. I want to only load the pixels into memory that I really need. I would like to avoid the processing effort involved in tiling the image.

Thanks for any kind of input!!