1. Add new database structure (new columns, new tables, whatever) but leave all the old structure in place
2. Update all servers with code that writes in the new format but understands how to read both the new and old structures
3. Migrate the data that only exists in the old structure
4. Get rid of the old stuff from the database
5. Get rid of the code that is responsible for reading the old format
Conceptually it's straightforward but it can take a long time in calendar days depending on your deployment schedule, it can be tough to keep track of what's been migrated, and the data migration will cause performance issues if you don't plan it properly (e.g. trying to do a migration that locks an important table). You just have do it in a way where each individual change is backward compatible and you don't move on to the next change until the previous one is rolled out everywhere.
its even worse if you want to be able to rollback.