The INDEX on DELETED is absolutely ok, if you do it as a BINARY index. The BINARY index is basically the rushmore map. Each record is represented as one bit, thus the resulting indexmap is way smaller and faster than the traditional indexing map.
[excessive quoting removed by server]