A sorted key-value store is implemented using a write-back cache maintained in memory, a B-tree data structured maintained in disk, and a logical and physical log for providing transactions. The logical log and write-back cache are used to answer client requests, while dirty blocks in the write-back cache are periodically flushed to disk using the physical log.