ol.Map.forEachFeatureAtPixel() actually already uses a R-Tree to speed up the search. But it is a bit more complicated. Intersecting the mouse-position with the features' geometry does not necessarily bring the result you would expect, because the styling of the features is totally ignored. E.g. if you click on a feature's icon, you would expect to select the feature. Because of that OpenLayers 3 is doing a pixel-based hit-detection.
The hit-detection works like this: First, all features that intersect with a buffer (
renderBuffer in ol.layer.Vector) around the pixel position are selected, taking advantage of the R-Tree that each vector source has. Then, one-by-one the draw operations of each feature are replayed on a 1x1 pixel canvas. After a feature is drawn, the color value of the 1x1 pixel canvas is read. If there is a value, it is a hit.
Usually the hit-detection is quite fast. But if you have really a lot of features and complex styling, it might be too slow. In that case you might consider to skip the exact pixel-based hit-detection and only do a bounding-box search. ol.source.Vector.html#forEachFeatureInExtent and ol.source.Vector.html#forEachFeatureIntersectingExtent will be useful in that case. Both methods make use of the internal R-Tree.