Deletes only remove the data from the primary index which exists in RAM (shared memory on enterprise). When you restart a node and it cannot reconnect to its previous primary index then it will need to rebuild the index from disk.
This issue is discussed here: How is data deleted?.