Eine typische Aufgabenstellung ist die Zuordnung einer IP-Adresse zu einer Geolocation. Verschiedene Anbieter veröffentlichen dazu Tabellen, die IP-Blöcke zu Regionen zuordnen. Wenn man jetzt eine IP hat, kann man z.B. folgende SQL-Abfrage benutzen, um den zugehörigen IP-Block zu finden:
SELECT block_id FROM ipblocks WHERE IP BETWEEN block_start
AND block_end;
Das Problem ist, daß so eine Query nicht effizient ausgeführt wird. Egal, ob man einen Index auf block_start, auf block_end oder auf beiden hat. Wenn die IP-Blöcke disjunkt sind - Start und Ende aufeinanderfolgender Blöcke sich also nicht überlappen - dann gibt es einen Trick, diese Query enorm zu beschleunigen...
"In welchem Intervall liegt mein Suchwert?"
vollständig lesen