The 3D variation of this question was asked recently: Scene Graph for Deferred Rendering Engine
I recommend a quadtree. Objects would typically best be represented by bounding boxes, rather than points (it always puzzles me that all the 'tutorials' seem to think games are made from point clouds). A node would contain four children - quadtree sub-nodes - and a list of those objects that straddle more than one child (which is way simpler than allowing objects to be in multiple nodes at once).
As items move they check to see if they are not fully-within their quadtree node's bounds and if not they remove themselves from their current node and then re-add themselves to the quadtree.
It is not uncommon to put projectiles and other very-fast-moving objects into a separate always-visit list or such, as adding and removing them constantly from the quadtree can hurt performance. An approach I favour though is adding the bounds of their flight in some number of game time steps to the quadtree. In this way they get moved around in the tree much more rarely, and they get found by all the nearest neighbour searches and such - this allows projectiles to actually hit things accidentally etc. It can dramatically simplify collision detection by not having several code paths and the interaction of several lists.
When rendering 3D you tend to want to draw front-to-back and opaque-then-transparent and in general this is true of 2D too, although you may know something about your artwork that lets you be less careful perhaps. So you take a frustum - or however you decide what is visible - and you cast this through your octree. This will be very fast.
You might want to hoist the list of currently visible items into the quadtree manager so that the frustum is painted onto the quadtree only when the camera moves, and bit-flags in the octree that track those sub-nodes that are fully-in-view or partially-in-view allow you to efficiently add and remove your visible items from the list.
At this point its all likely so blazingly fast - compared to your rendering cost - that you don't need to optimise it further with all the various special cases when moving things around and such, or deferred re-sorting of changing visibility lists and such.