Efficient beam training is the key challenge in the codebook-based configuration of reconfigurable intelligent surfaces (RISs) because the beam training overhead can have a strong impact on the achievable system performance. In this paper, we study the performance tradeoff between overhead and achievable signal-to-noise ratio (SNR) in RIS beam training while taking into account the size of the targeted coverage area, the RIS response time, and the delay for feedback transmissions. Thereby, we consider three common beam training strategies: full search (FS), hierarchical search (HS), and tracking-based search (TS). Our analysis shows that the codebook-based illumination of a given coverage area can be realized with wide- or narrow-beam designs, which result in two different scaling laws for the achievable SNR. Similarly, there are two regimes for the overhead, where the number of pilot symbols required for reliable beam training is dependent on and independent of the SNR, respectively. Based on these insights, we investigate the impact of the beam training overhead on the effective rate and provide an upper bound on the user velocity for which the overhead is negligible. Moreover, when the overhead is not negligible, we show that TS beam training achieves higher effective rates than HS and FS beam training, while HS beam training may or may not outperform FS beam training, depending on the RIS response time, feedback delay, and codebook size. Finally, we present numerical simulation results that verify our theoretical analysis. In particular, our results confirm the existence of the proposed regimes, reveal that fast RISs can lead to negligible overhead for FS beam training, and show that large feedback delays can significantly reduce the performance for HS beam training.