indexes, foreign keys and optimization
In the example you show, the expression would use the index on criteria to resolve which rows to retrieve, and the leaf nodes in the index contain references to the corresponding rows, either by physical location in the case of MyISAM or by primary key value in the case of InnoDB.  That way it avoids a full table scan.
Note that if the query optimizer thinks your query matches too much of the table, it will ignore the index, because it's just as fast to do the table-scan.  By analogy, this is why no one bothers to put the word &quot;the&quot; in the index at the back of a book.

No, MySQL requires that an index exists for the foreign key.  If an index already exists, InnoDB will use it, but it will create one if necessary.  I have found some corner cases where you can trick InnoDB by dropping the index after defining the foreign key constraint, but this would not be advisable, because the index is important for checking referential integrity quickly.

It's true that insert/update/delete needs to update indexes to reflect values added or removed.  But it's not as bad as you might fear.  Also, InnoDB implements a &quot;change buffer&quot; which records how your update affects secondary indexes, and reconciles it with the whole index later.

InnoDB and MyISAM support only BTREE indexes.  InnoDB also has an internal feature called the adaptive hash which does do a hash lookup for frequently-requested index entries.  But this is completely automatic and transparent; you don't have to define any index or tune any config parameters.