How to implement soft deletes? What is your method of implementing soft deletes in a database?

Ideally the solution would allow for


decent performance on large tables
take relationships into account
take unique keys into account
the user should be able to find and restore his deleted items.


Thanks!
There's a couple of ways I can think of to do it:


You could have a "Deleted" indicator, which is set to "Y" when a record is deleted. Very simple, but it leaves deleted and active data in the same tables, which could cause performance problems if there's a lot of activity. Restoring a record is as simple as changing the indicator.
You could have a table that mirrors the structure of the one you want to delete from, and when you delete a record from the main table, insert that record into the "deleted_data" table. This allows you to move deleted data into separate table to give the main table better potential performance, but searching for data that is in either table could make things more complicated, and keeping the data structures in sync  (when they change) is also a bit more work that has to be done. In this case, restoring the data would involve removing the record from the "deleted" table and inserting it back into the main table.


In both cases, you may want to find any child records and mark them as deleted as well. I suppose you could do this with triggers or with code.