A database recovery and index rebuilding method involves reading data pages for a database to be recovered as recovery bases; retrieving all log records from stored post-backup updates and sorting the retrieved log records; as the data pages to be recovered are read, applying the sorted log records to their respective data pages; as the applying completes for individual data pages, extracting and sorting index keys from the individual data pages for which the applying is complete, until all index keys have been extracted from all individual data pages and sorted; on an individual recovered page basis, writing the recovered individual data pages into the database; and when all index keys have been extracted and sorted from all of the recovered individual data pages, rebuilding indexes of the database using the sorted index keys and writing the rebuilt indexes to the non-transitory storage.