Martin,

Actually, what Barbara said is that the index on DELETED() may speed things up. Whether there is a gain or loss in speed is a very individual thing and should be tested for each application. The same applies on any index for a field which has only a few discrete values, such as gender.

Note that a proper test involves turning the machine off between tests, due to cacheing.

>As our dear Barbara said, keep an index on deleted()