In one embodiment, a method includes receiving a request to perform an update on a base data set in a record-oriented file system, locate all alternate index (AIX) records for the base data set, each AIX record including an alternate key field along with one or more relative byte address (RBA) values when the base data set is an entry sequenced data set (ESDS) or one or more primary keys when the base data set is a key sequenced data set (KSDS). Each RBA value/primary key corresponds to one record in the base data set. Individual record-level locks are acquired on each affected AIX record that includes alternate key field values and/or RBA values that are modified by the update. The affected AIX records may be updated after acquiring the individual record-level locks on each of the affected AIX records. Moreover, the affected AIX records may be updated in parallel with updating of unaffected AIX records, thereby greatly increasing performance.