algorithms and datastructures

/prog/ i have a problem

for the past couple of years i have been fooling myself into
thinking i am a programmer. i would pick up a new language every
few months, write a few toy programs in it and convince myself
that, since i knew how to write fibs, i knew how to make
something.

turns out all i'm capable of doing is shoveling data back and
forth between the user and some API. i am not capable of
designing complicated data-structures or algorithms to
query/modify them.

i have come to that conclusion when i was faced with some
problems regarding the design of my /prog/ roguelike server. i
wanted something that scaled better than my current solution: a
simple list of (x,y,entity). i quickly found myself humbled in
the land of spatial databases.

so /prog/, how would i go about saving loads of entities? i
already have a tile map[x][y] but i might want to
have lot's of entities of a single tile (dead body, armour,
weapon, gold) so i can't just add an entity pointer to tile.
also i want to keep my tile small (one or two bytes) so i can
have bigger maps. i'll need to make something like a quadtree
but what if i want to have a shittun of items in the same place
and my nodes overflow?

>>5
yeah, everything is abstracted, don't worry :-)

my main problem with the idea of using a single list (or adding a linked list to map[][] like >>4 suggested) is the complexity of finding all entities in a certain region: using a simple single list this is O(N) w.r.t. the total amount of entities, >>4-san's solution is O(N) w.r.t. the size of the area being queried, same with using bins.

i'd prefer to sacrifice some space to get some more performance.