Getting multigrid software to solve for as many unknowns per second as possible on current high performance computers means designing its data access patterns to be as regular as possible. Regularly structured data allows for optimally exploiting the processor capabilities (e.g. vector processing) and the interconnection network (e.g. by grouping communication operations). Just as important as solving for many unknowns in short time is reducing the overall number of unknowns. Adaptive mesh refinement (AMR) can significantly reduce the problem size in many cases. However, this technique is known to impede the use of regular data structures, and, thus, to drastically restrict the possible performance of the solver. In our talk we show how AMR can be implemented without destroying the regularity of the data structures, maintaining a fast execution. The framework for the AMR implementation is provided by Hierarchical Hybrid Grids (HHG), a multigrid finite element solver designed for the use on massively parallel computers with several thousand processors. The software uses semi-structured meshes in order to achieve high performance on such computers. In the talk both red-green refinement and refinement with hanging nodes are covered, because both methods have individual advantages, and the decision for one of the methods--or for a combination of both--has to be made depending on the problem characteristics. We develop the mathematical foundation for using AMR with the correction scheme, and we show its feasibility in practical examples.