A storage node of a database replica group may distribute different portions of data in local storage and external storage, where local storage and external storage are organized using different types of index structures. Responsive to receiving an access request for a database, a storage node may determine that an item of the database to be accessed by the request does not reside within a first portion of the database stored locally at the storage node. Responsive to this determination, the storage node may obtain from an external storage service a second portion of the database, the second portion including a plurality of items including the item, and the second portion organized according to a structure different from the first portion. The storage node may then store the plurality of obtained items in the first portion and process the request using the first portion of the database.