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