It's almost a rule of thumb to avoid indexing strategies on tables with less than a few thousand rows. The reason, of course, is that SQL Server will frequently just ignore indexes on 'tiny' tables - preferring instead to perform table scans.

However, in environments with heavy load, and with borderline memory bottlenecks (i.e. heavy memory pressure), indexing can prove VERY beneficial, even on absolutely puny tables (as in less than 600 rows).

During some recent performance monitoring/tuning for a client with a 160GB+ database which typically has > 2400 users on it at any given time, I noticed that two queries tied to scheduling and custom template 'goodness' were generating more than their fair share of READS. (These two queries accounted for 17% of all calls on the system, and > 35% of all of the reads on the system.) As is typically the case, I have NO control over the underlying code (it's a third-party system), but still need to keep things performant.

A big problem was a bookmark lookup, against a 'small' table with roughly 120k rows in it. It was generating a very large number of reads. By tweaking the existing clustered index to make it cover better, I was able to reduce the total cost of both queries down significantly. Then, I noticed a number of other Bookmarks, and decided to take a stab at them. When everything was said and done, I was able to cut the cost of both queries to roughly HALF of what it was before. Granted, a sizeable portion of that was because of the covering index on my 'small' table, but the covering indexes on my 'tiny' tables helped out as well.

Empirical speak:

Original Cost of both Queries:

Added Covering Index to 'small table' (~120k rows):

Covering Index also added to a <500 row table:

Covering Index also added to a ~600 row table:
.114 (not much of a boost)

Covering Index also added to a table with a whopping 364 rows:
.099 (nice boost!)

The beauty (other than seeing what amounted to a 50% reduction in overall cost) is the fact that indexes on such piddly tables are almost free - they certainly won't be taking up much space at all. (These were just standard/normal lookup tables - nothing hideous/super-wide).

So, keep micro-indexing in mind. Without micro-indexing I would have seen a drop from .176 down to .140 - a significant boost on such a heavily used system. But with micro-indexing I gained another significant performance boost.