So, basically the already-existing Visibility Map?

Indexes in postgres point to the page, not the tuple. The VM keeps two bits per page: "does this page have any 'dead' tuples?", and "does this page need to be touched for xid wraparound?"

Vacuuming doesn't touch a page unless the VM indicates it's necessary.