One thing I didn't see anyone mention is size. An index is likely (not necessarily, of course) smaller than the table, so even in the worst case of a full scan of the index, the amount of data passed around from the disk subsystem should be smaller. Seems like that should be worth something.