Mechanisms are provided for optimizing random access in a storage system. According to various embodiments, an access pattern may be identified for a plurality of data segments stored in a first arrangement on a storage medium. Each of the plurality of data segments may be stored at a respective first storage location on the storage medium in the first arrangement. The access pattern may indicate an order in which the data segments are likely to be retrieved from the storage medium. The plurality of data segments may be stored in a second arrangement on the storage medium based on the identified access pattern. Each of the plurality of data segments may be stored at a respective second storage location on the storage medium in the updated arrangement.