I usually don't like the "read the article" replies, but in this case it's warranted - the second section explains how multiple transactions interact there, and the "deleted" record still needs to actually exist for older transactions.