Embodiments of the invention relate to organizing data records in a relational database. An aspect of the invention includes creating index items for a plurality of data records. Each index item includes a counter and the creating results in a plurality of counters. The numerical values of counters in corresponding index items are updated for data records in the plurality of data records that are subjected to random access. The plurality of data records are reorganized based upon the numerical values of the plurality of counters.