Methods, non-transitory machine readable media, and computing devices that provide file backup catalogs with improved scalability are disclosed. With this technology, a sequence number is incremented and an entry for a snapshot associated with obtained metadata for the snapshot is generated. The snapshot entry comprises a snapshot identifier for the snapshot and the incremented sequence number. A current version flag is then set in another entry for a file associated with a create event identified in the metadata. The file entry includes a file identifier for the file, a create attribute comprising the incremented sequence number, and a delete attribute. The file and snapshot entries are then inserted into indice(s) in a catalog database. Based on the schema of the indice(s), this technology provides a lightweight, elegant, and highly scalable catalog that more efficiently facilitates full path global file search and restore functionality with reduced resource utilization.