So far, I’ve analyzed point and range queries. Now it’s time to talk about insertions and deletions. We’ll call the combination updates. Updates come in two flavors, and today we’ll cover both.
Depending on the exact settings of your database, the updates give a varying amount of feedback. For example, when a key is deleted, all rows with that key are deleted (assuming the database allows duplicate keys). The normal behavior is to return the number of rows deleted. The normal behavior when deleting a key that has no corresponding rows in the database is to return an error message. On insertion, one can allow duplicate or not. In the latter case, the storage engine returns an error message if a duplication insertion is attempted.
We’ll see that the details of error messages have a profound influence on the lower-bound arguments I’ve been making (and we’ll see a bit …[Read more]