Cindy,

A minor correction, the issue is not how many different values the field many have, it is the distribution of those values. For example, a gender field for a table of 1,000,000 records that is used to stored the students registered at Vassar may not be a good candidate for an index because 99.999999999% of the fields are F. However the same field for a table of students registered at UCONN may indeed benefit from an index as the distribution of values is more even.

The issue of the index on deleted is that in most situations the distribution of values for deleted is heavily uneven in favor of the non-deleted records.