Large tile storage for multiplayer online games

Question

I am currently creating a tile based morpg and am trying to find a good way to store a large 2nd game world (at least 1000 squares, but hopefully more like a few thousand squares). The idea is to encourage people to create their own cities on a shared map, and users can create homes and stores so that they can be edited and have a one-to-many relationship with some related tables. I am going to send them to the client in pieces of fragments of size 64x64.

I am currently working in php / mysql, my table looks like this:

CREATE TABLE `fbmmo`.`tiles` ( `id` int(10) unsigned NOT NULL AUTO_INCREMENT, `x` int(11) NOT NULL, `y` int(11) NOT NULL, `realm` varchar(45) NOT NULL, `image_id` varchar(45) NOT NULL, PRIMARY KEY (`id`), KEY `Index_X` (`x`), KEY `Index_Y` (`y`) ) ENGINE=InnoDB AUTO_INCREMENT=4327236 DEFAULT CHARSET=latin1; 

and queries are something like

 select * from tiles where x<1000 and y<1000 and x>936 and y>936; 

When I have only half a million records, it takes only half a second, but when I get about 4 million records, it takes about 5 seconds, and I'm sure this is a way to improve this.

I can get around it by caching map requests, but I wondered if there is a better way to set up the database, and also if anyone has tips on efficiently storing a large 2nd game world?

thank you for your time

Answer 1

As the size of the data set increases, range queries can quickly get out of hand. You might want to look at the literature. Here are some interesting works.

Data structures for range queries:

http://portal.acm.org/citation.cfm?id=1035798

www.siam.org/proceedings/soda/2010/SODA10_014_yuanh.pdf

Quick Search Algorithms

www.cccg.ca/proceedings/2005/3.pdf

Answer 2

Perhaps you could cut the fragments already at the database level?

Answer 3

Just my little 2 cents. Perhaps, depending on how ppl scrolls the map, you can pre-select the following N sets of 64x64 sets. A bit about image_id varchar (45) NOT NULL, are you sure you want to keep the kingdom in each tile? Could you imagine why this is good.