What level of indexing is sufficient depends a great deal on the specifics of the database layout on disk. In InnoDB for example, sequential scans are very costly, and primary key lookups are very cheap. This is because the table is more or less contained in the primary key index and this must be traversed in key order since physical order is not supported. This means a sequential scan of a table means lots of random disk I/O and OS prefetching is useless.

So to address this you end up indexing everything you want to search on later. Note that non-pk indexes are a little slower in InnoDB because you have to traverse the index to find the primary key value, then you have to traverse the primary key index to retrieve the table info.

In PostgreSQL things work differently. The table is a series of pages on disk and rows are allocated from these as a heap. You can scan a table, but not an index, in physical order in PostgreSQL. Therefore typically PostgreSQL sequential scans on tables are lot faster than on MySQL because it is sequential, rather than random, page reads. Indexes point at the tuple ID which stores the page number and row number within a page. An index scan is a tree traversal followed by processing pages indicated in the tuple ID.

This leads to a bunch of interesting things: Adding indexes is usually a performance win with InnoDB. However for PostgreSQL, it will typically look up what indexes it has and balance index scans against sequential scans of tables. Unlike InnoDB, sequential scans sometimes win out planner-wise, esp. on small tables.

So what indexes you need depends quite highly on how things are organized.