If the index consists of a b+-tree/b*-tree interleaved with the data (with the root of the index the last record in the archive), a single backward pass across the tape (including rapid seeks to skip irrelevant data) is sufficient to efficiently restore everything. This should be very close in throughput and latency to restoring with an index on random-access storage. (Though, if you're restoring to a filesystem that doesn't support sparse files, writing the data back in reverse order is going to involve twice as much write traffic. On a side note, I've heard HFS+ supports efficient prepending of data to files.)

In other words, yes, you need to scan the tape to reconstruct the catalog, but since the tape isn't random access, you need to scan/seek through the entire tape anyway (even if you have a separate index on random-access media). If you're smart about your data structures, it can all be done in a single backward pass over the tape (with no forward pass). Keeping a second b+-tree/b*-tree interleaved with the data (keyed by archive write time) makes point-in-time snapshot backups just as easy, all with a single reverse pass over the tape and efficient seeks across unneeded sections of tape.