I see galleries are represented as separate post records with
post_type = 'gallery' in the database.
How is this record (gallery) associated with a basic post (
type = 'post') in the terms of database records?
If you have a custom post type called 'gallery', you should be able to find it fairly easy if you can browse the database directly with phpMyAdmin. You will see your database tables on the left side of phpMyAdmin. Click on your posts tables which will probably look like "wp_posts". This will display a list of tables. Click the search icon at the top. Scroll down to the post_type field and enter "gallery". Press enter or click the "Go" button below. This should result in a list of every custom post_type in your database. Click "edit" for any table you wish to view. There you will see all of the details such as the ID for this post or the post_parent, which may be what you are looking for.
I do not have a gallery post_type, but if I want to know which post and image is related to I can search for the image within the post_type 'attachment' and even refine my search by using the specific image ID if I know it. Then I can "edit" the image and find the post parent.
By the way, you can get the ID of an image, post or anything else by going to its edit page in the admin panel and looking at the url. You will see something like "post=xxx" where xxx is the post ID.