I investigated similar data structures some time ago when I looked into broad-phase collision detection. A variation of k-d trees (http://en.wikipedia.org/wiki/Kd-tree
) could be a possibility for tiles. k-d trees are normally just for points, but it is possible to modify them to support bounding boxes, meaning that you could skip the distance check that you would need for the quad tree. While I recall they are relatively expensive to create and modify, meaning quad trees would likely be a better solution for moving objects, you rarely need to modify tiles, and they should have decent performance for querying areas of tiles (especially tiles that have regular sizes and are spread out in somewhat uniform density). That said, I don't know how much of a speed up it would provide, unless the room with tiles is very, very large relative to the view, in which case I think it could be well worth it.
As for collision detection, I think they can easily be worth it, given that the number of collision can be quadratic in the number of instances (if you have two about equally large groups of instances where the groups collide with each other), and a k-d tree should in most cases reduce the number of collision from O(N^2) to O(N*log(N)) or something similar.