Index cards, in locked file cabinets, in a locked room.
A level of complexity most organisations can handle without major screwups.
BTW, backup copies and keeping track of them: when the GDR went down, the MfS* made sure that the HVA** erased their files on agents in the west*** working for them (double agents, infiltration agents, people blackmailed into working for them, etc). However, sometime in the mid-1980ies the HVA had upgraded their computer systems and before doing so, they made a full backup of the data on the old systems. After the new systems were operational and had been fed the data from the old systems, both the old systems and the backup were destroyed. Due to an oversight, one of the redundant copies of the backup survived and was found while sifting through the Stasi's leftovers, so to speak. The tapes could be read with the help of a collector who had old Robotron mainframe gear (originally used by the GDR's post office) in his garage; actually the only surviving hardware capable of doing so.
* Ministerium für Staatssicherheit (= Ministry of State Security), or "Stasi" for short.
** Hauptverwaltung Aufklärung. The department in charge of spying on foreign countries, run by Markus Wolf.
*** They made damn sure however they didn't erase what they knew about their West German counterpart, the BND. Word is, the BND analysts viewing the material came pretty close to having heart attacks several times.