Random access to run-length encoded data values is provided. A target value is identified by a logical index into a structure of run-length-encoded values. To access the value, a bookmark is selected based on the logical index, on a maximum logical index of the bookmark, and on a specified bookmark distance. An initial run in the structure is located, based on the selected bookmark. A final run is chosen, at most one bookmark distance from the initial run. The target value is the value of the final run. Efficiency heuristics are used when generating bookmarks or creating the structure of run-length-encoded values.