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?

For a second I thought this was going to be interesting.
It's all about how you're going to access things, but you can do >>4, or a variation with time/space tradeoff by binning things into larger areas.
You certainly don't need a quadtree to store entities for your roguelike. Though similar structures could be useful to generate and store map data if maps are sparsely featured.
I hope you have this all abstracted, so you can start with a simple implementation and swap it out later.