Specifically, what tables are created and/or affected by these two actions (re-indexing products or flushing categories), and what visibility elements specifically depend on this. I.e., what will re-indexing products and/or flushing categories NOT have an effect on?
Magento uses the EAV (Entity Attribute Value) method. This means that every attribute you add to a product or category, is saved in a separate table (eav_attribute and catalog_eav_attribute).
When creating a product, it will load all linked attributes, so you can add values to them. After saving the product, all the values will be saved to separate tables as well catalog_product_entity_*.
When not using flat tables, every time the product is loaded, it will have to get the main entity table (catalog_product_entity) and all linked tables as described above. This can take some time, because by default a product already has a lot of attributes. To make this faster, you can use the flat tables in Magento, both for categories and products. When enabled, you can reindex the category and product indexes.
All attributes that are either set to "Used in Product Listing", "Use in Quick Search", "Use in Advanced Search" or "Used for Sorting in Product Listing" will be used for this flat tables.
Every store view has his own flat table for categories and products. When reindexing every attribute matching the criteria mentioned above will be "converted" to a column in the flat table. Every attribute value will be set as the value for that column. So after reindexing has been completed, all data for a product or category is available in one single table. This increases the speed in which Magento can search and fetch products from the database. Every time you do a reindex, it will rebuild the flat table(s).
