The invention provides an efficient apparatus and method for deleting items within a distributed datastore. Deletion of items is accomplished using anti-items having the same structure as a conventional data item, but for a single tag, flag, or bit which indicates that it is an anti-item, wherein the single tag, flag, or bit but does not affect the location at which a data item or anti-item is ultimately stored within the datastore, thereby ensuring that, upon insertion, the anti-item reaches the same location or locations within the datastore as the original data item.