3d - Data Structure (or algorithm) for fast distance-based entity lookups

For example, your game has 100 enemies (on different teams) running around and their AI wants to inspect the nearby entities to see which it should attack. What is a fast way to organize those entities so that each enemy does not have to calculate the distance between itself and all other entities?

In short, what is a fast way for an AI entity to answer the question "Who is near me?"

Answer

You want a spatial index such as quadtree (2D) or octree (3D).