Each record gets its own data key (DEK), stored wrapped by a key-encryption key (KEK) together with the KEK id. Rotating the KEK only rewraps the small DEKs, not the data.
Envelope encryption
Encrypting data with a random per-record key that is itself encrypted by a master key.