I’ve been waving my hands about lower bounds. Well, sometimes I haven’t been waving my hands, because the lower bounds are tight. But in other cases (lenient insertions, range queries), the lower bounds are very far from what we’re used to.
So now, for a bit of math:
Brodal and Fagerberg showed in 2003 […]
Sorry for the delay, now on to range queries and lenient updates. Let’s call them queries and updates, for short. So far, I’ve shown that B-trees (and any of a number of other data structures) are very far from the “tight bound.” I’ll say a bound is a tight if it’s […]
Read more
Probably most of MySQL users sometimes had a situation when they would do changes in MySQL config file without restarting the server (maybe matching SET GLOBAL command to do it in run time). This could be because it is misspelled or because the given version does not support such option, the server when would […]
Read moreLast time, I introduced the notion of strict and lenient updates. Now it’s time to see what the performance characteristics are of each.
Just to rehash, we are focusing on the storage engine (a la MySQL) level, and we are looking at a database on a single disk — the one we are using […]
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 […]
