1. A system, comprising: one or more block-based persistent storage devices, configured to maintain a plurality of data chunks that together comprise a dataset as part of a relational data store, wherein individual ones of the plurality of data chunks correspond to a respective one or more storage locations at the one or more block-based persistent storage devices, wherein the respective storage locations for the plurality of data chunks are linked together according to an ordering schema that specifies a sort order according to a data value of the dataset such that data of the dataset for the relational data store is stored across the respective linked storage locations according to the sort order of the ordering schema for servicing queries; at least one processor; a memory, comprising program instructions that when executed cause the at least one processor to implement a storage manager; the storage manager, configured to: for individual ones of the plurality of data chunks: generate an updated version of the data chunk in one or more new storage locations at the block-based persistent storage device that are not included among the respective storage locations for the plurality of data chunks, wherein the generation of the updated version of the data chunk applies at least one data value insertion or deletion to the data chunk such that data of the updated version of the data chunk is stored within the one or more new storage locations according to the sort order of the ordering schema, wherein the plurality of data chunks including the data chunk are available to service queries during the generation of the updated version of the data chunk; in response to the generation of the updated version of the data chunk: replace the respective one or more storage locations corresponding to the data chunk with the one or more new storage locations storing the updated version of the data chunk in order to link the one or more new storage locations together in the sort order with remaining ones of the respective storage locations for the plurality of data chunks, wherein subsequent queries are serviced from the plurality of data chunks including the updated version of the data chunk; and reclaim the respective one or more storage locations for the data chunk to store other data.