You just do it the way fast storage wipes do it. Encrypt everything, and to delete you delete the decryption key. If a user wants to clear their personal data, you delete their decryption key and all of their data is burned without having to physically modify it.
That only works if you have a single key at the block level, like an encryption key per file. It essentially doesn’t work for data that is finely mixed with different keys such as in a database. Encryption works on byte blocks, 16-bytes in the case of AES. Modern data representations interleave data at the bit level for performance and efficiency reasons. How do you encrypt a block with several users data in it? Separating these out into individual blocks is extremely expensive in several dimensions.
There have been several attempts to build e.g. databases that worked this way. The performance and scalability was so poor compared to normal databases that they were essentially unusable.