I would recommend to read this on indexes: http://en.wikipedia.org/wiki/Index_(database).
Simply put, a database engine creates a new structure which keeps the indexed column (which corresponds to a property) sorted and a link to the corresponding row for each entry (primary key). This allows for faster searches (since search in ordered lists is faster than in unordered lists). But this increases used storage (for the data structure), and insertion times (to keep the structure sorted).
So yes, you should use indexes in such cases.