The way to go searching in such a database is probaby to store the whole dataset in fixed-length records and then using binary search. It's trivial and fast.
Edit: if you make sure entries are sorted and every entry has an unique incremental contiguous ID then you can even implement binary search via SQL itself with just few primary key lookups (few = log_2(N))
Btw, if you really need high performance here use a key-value DB and just store all the 2^24 entries (16 million), then just drop the last ".xxx" from the IP and perform a single lookup that will return the "id" of the place. Then retrieve place:<id> key to get the real location.
Btw, if you really need high performance here use a key-value DB
Or a real relational database configured with a "key" column and a "value" column and let the wonders of proper clustering and indexing provide you with the data in realtime no matter what load you put on it, because this dataset is shit tiny.
No really. I'm dead serious.
If you feel like optimizing this further, you can ofcourse also save memory by shifting countries and cities to separate tables, this reducing the size of the dataset noticeably, maybe by up to 40%.
I'm just shaking my head at all the "database problems" MySQL users invent to excuse their choice of subpar DB.
http://www.hostip.info/dl/index.html has a SQL database as well. Their database is broken up in to 255 tables (for each of the first octet, and each table consists of the fields corresponding to the 2nd and 3rd octet.
Recently I made a traceroute visualization mashup with their database (http://www.janitha.com/geoiptracer) just enter a list of IP's and it will draw lines connecting them in order.
Talking about geolocation, another shameless plug for my weekend project, a phonenumber-geolocation mashup http://www.janitha.com/telmapper
Yeah so he reduced the number of database rows from 3M to 1.4M. But you shouldn't be using a normal database for this type of query anyways - it's SLOW, because you're doing a range search. Maxmind also offers a binary database that is extremely fast, even with just a PHP script that they provide that parses through it - and I guarantee you this is at least 10 times as fast as doing it with MySQL. And if you install their Apache module, which is not hard (although you do need root access on the machine), it's something like 20x to 30x faster.
Not to put down this person's/people's work, but don't do IP geolocation with MySQL if performance is of any importance to you. Use the binary database that Maxmind provides and you can get much better performance with almost no extra effort.
You bring up a good point, but distributing this as a database is a convenient interchange format. It means I can quickly start playing around with it to see how accurate and precise it is. I downloaded it, imported it into a test database, and was querying it in under 2 minutes. It took me longer than that just to figure out what sort of license I would need to use Maxmind.
But you shouldn't be using a normal database for this type of query anyways - it's SLOW, because you're doing a range search
Please explain to me why databases is a bad choice for data which you wish to retrieve in ranges.
If you've clustered, stored and pre-sorted the data according to the range you wish to extract, this is probably the fastest way on the planet to retrieve the data.
Or is this simply more of that good, old MySQLism? You know, the "MySQL can't do it efficiently, so databases sucks"-mantra?
but don't do IP geolocation with MySQL if performance is of any importance to you.
If you remove the "IP geolocation with" part, I think we have a winner.
Edit: if you make sure entries are sorted and every entry has an unique incremental contiguous ID then you can even implement binary search via SQL itself with just few primary key lookups (few = log_2(N))
Btw, if you really need high performance here use a key-value DB and just store all the 2^24 entries (16 million), then just drop the last ".xxx" from the IP and perform a single lookup that will return the "id" of the place. Then retrieve place:<id> key to get the real location.