Sure, you can trivially design a data structure where insert and delete have the same cost. This works if you don’t care about query performance; most people ca

Sure, you can trivially design a data structure where insert and delete have the same cost. This works if you don’t care about query performance; most people care about query performance a great deal. This was litigated in the marketplace decades ago. Even every open source database rejects designs that produce rubbish query performance. It also does not reflect the real-world distribution of operations between insert and delete — we do a lot more inserts. The “erase-in-place” operations you mention were common in databases a few decades ago and abandoned because the typical performance was terrible compared to the alternative. I am old enough I even implemented a few. It isn’t like these designs didn’t exist, they were deeply flawed for reasons that apply today. This has nothing to do with perfection. Database engineers would love if deletes where inexpensive even in the absence of hard delete requirements, as that would make update operations, which people want, dramatically cheaper. But that isn’t the reality. You are essentially re-litigating settled database kernel engineering without understanding why they are designed the way they are. If you thinking there is “low hanging fruit dragging on the ground” then I encourage you to prove it by designing a useful database kernel that can scale deletes while preserving insert and query performance, the two operations that drive all economics in databases. You’ll be instantly famous as a computer scientist because there are some nasty theoretical computer science problems in there.