The disclosed embodiments relate to the design of an append-only data storage system that stores sets of data blocks in extents that are located in storage devices in the system. During operation of the system, when an extent becomes full, the system changing the extent from an open state, wherein data can be appended to the extent, to a closed state, wherein data cannot be appended to the extent. Changing the extent from the open state to the closed state includes performing the following operations at one or more storage devices that contain copies of the extent: constructing an index to facilitate accessing data blocks in a copy of the extent contained in the storage device; and appending the index to the copy of the extent in non-volatile storage in the storage device.