This is a basic question in ray tracing. Do a Google search on "ray tracing acceleration data structures," or pick up a copy of the PBRT book by Pharr & Humphreys. Classic examples of acceleration structures include the kd-tree and bounding volume hierarchy (BVH). Although kd-trees are theoretically optimal in many situations, actual performance depends largely on the distribution of triangle sizes and locations. You also need to take into account the complexity of building the structure -- building a kd-tree nominally takes O(n log n) time in the number of triangles, but it is difficult to make incremental updates (e.g., for dynamic geometry). A more modern acceleration structure is the BIH (bounding interval hierarchy), which is useful for dynamic scenes.
(Also, a resource more specific to your problem than stackoverflow.net are the forums on ompf.org)