This paper describes a novel framework for autonomous exploration in large and complex environments. We show that the framework is efficient as a result of its hierarchical structure, where at one level it maintains a sparse representation of the environment and at another level, a dense representation is used within a local planning horizon around the robot. The exploration path is computed at the two levels, coarsely at the global scale and finely around the robot. Such a framework produces detailed paths in the vicinity of the robot, while trades off data resolution far away from the robot for computational efficiency. In experiments, we evaluate our method with a real robot exploring large and complex indoor and outdoor environments. Results show that our method is twice as efficient in covering spaces while using less than one-fifth of processing in comparison to state-of-the-art methods.