A method for operating a data storage system that is comprised of at least one disk. The method includes a step of partitioning a data compression unit into n basic compression units, where n is greater than one. Each data compression unit is comprised of a plurality of disk sectors and each of n basic compression units begins with a different initial sector. A next step partitions the data compression unit into X intervals, where X is less than n. Each of the X intervals begins with a different initial sector and within one of the n basic compression units. Further steps of the method include storing, external to the at least one disk, a plurality of first pointers each of which points to the initial sector of one of the n basic compression units wherein the 1/X, 2/X, . . . , (X-1)/X intervals begin; storing, within each of the initial sectors of the individual ones of the n basic compression units wherein the 1/X, 2/X, . . . , (X-1)/X intervals begin, a second pointer to the initial sector of the interval that begins within the basic compression unit; and, in response to a disk read operation that reads a compressed data unit that begins with one of the sectors that is located within one of the X intervals, accessing the beginning sector of the compressed data unit in accordance with one of the first pointers and one of the second pointers. The step of allocating includes a step of determining an actual compression ratio for the record, determining a value of a longest run of identical characters within the record, and adjusting the actual compression ratio based on the value of the longest run of identical characters. The step of allocating also includes a step of adding at least one additional sector to the estimated number to enable the compressed record to be subsequently updated in place.