How does Android keep track of if an app has been installed before?

I'm trying to find if there's a location within root where your phone keeps a record of what apps have been installed on your phone, like maybe a database. As a secondary question I'm also trying to find for instance where a game would keep local game saves. I did a test where I installed a game that I had played before, so the default local game save is where I left off. Uninstalled it with SD Maid and double checked data/data for the package name and it was deleted. Reinstalled the app and it had retained the last game save, so it obviously knows it had been installed previously. A factory reset clears any record of an app having been installed, since by doing that, your phone is considered a different device. Anyways, after uninstalling again, I tried doing a

/ -name *packagename* > sdcard/output.txt

and only ended up with 3 results:

/data_mirror/data_ce/null/0/com.google.android.gms/files/backup_chunk_listings/
/data/user/0/com.google.android.gms/files/backup_chunk_listings/
/data/data/com.google.android.gms/files/backup_chunk_listings/

I assume the save game data would be somewhere on /data/ but no idea where. As for a record of what apps the phone has installed, I have no idea where that would be, my only guess was

/data/com.google.android.gms/databases/