A single AES encryption block is 16 bytes; internal storage of records is managed in terms of individual bits if you don't encrypt them. You also can't compress data encrypted in this way, which is table stakes for databases. The encryption key schedule alone for a single record will be much larger than the typical record! Requiring a per-user encryption key has the unfortunate effect of bloating database storage and memory requirements by at least 10x, while massively reducing computational throughput.
The design of delete-efficient database kernels is an interesting unsolved problem in computer science. No one knows how to do it. People that think there are trivial solutions have not studied the problem adequately. It hasn't been a priority to solve this problem, but its reputation for being theoretically difficult is well-deserved.