From computer science
, this is the notion of tagging an item to be ignore
d instead of actually deleting it. When an algorithm traverse
s down a tree (or other data structure) and hits a node
that is tagged, it procedes through the traversal
without considering the item. Periodically, the data structure
in question is rebuilt with the tagged data excluded. Often this is done when the percentage
of deleted nodes reaches a threshold
(say, 10%), or after a certain amount of time
You use a lazy delete in structures which take a prohibitively long time to do a real delete. In trees, for instance, you not only have to find the node and delete it, but do processing farther down in the tree to fill in the empty node created. Balanced trees (such as the AVL tree) are even worse, as the tree needs to be rebalanced after each real delete.
Lazy deletes may strike you as inelegant, but when you consider how much larger the worst case complexity for a delete operation can be than a find operation (O(n lg n) as opposed to O(lg n), etc.), they starts making much more sense.