Data Structure – For online multiplayer game storage large-scale map-based map

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;

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

I am currently making a tile based on mmorpg and I am trying to find A good way to store large 2D game worlds (at least 1,000 square tiles, but hopefully more like a few thousand squares). The idea is to encourage people to build their own cities on a shared map, and users will be able to build houses and shops in order to be able to Edit tiles and have a one-to-many relationship with some linked tables. I am considering sending them to the client in the form of 64×64 tiles.

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

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;

It is roughly similar to query

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

When I only have about half a million records, it only takes about half a second, but when I reach about 4 million records , It takes about 5 seconds, and I am sure there are some ways to improve it.

I can solve this problem by caching the map request, but I want to know if there is a better way to configure the database, And does anyone have any tips for effectively storing large 2D game worlds?

Thank you for your time

As the size of the data set increases, range queries can get out of control very quickly. You may want to see Some literature about this. Here are some interesting papers.

Data structure of range query:

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

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

Algorithms for quick search

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