Concept maps are assumed to enhance learning as their inherent structure makes relations between information more salient. Nevertheless, research on how to design concept maps as conducive to learning as possible is still rare. In particular, the salience of spatial arrangement of thematically related concepts within the map as well as the complexity of the map were found to be central design elements that influence learning. This study aimed to examine how the structure (i.e., the salience of the spatial relationship between individual concepts) and the complexity (i.e., number of nodes per sub concept) influence learning. Accordingly, a 2 (low vs. high salience of map structure) × 2 (few vs. many nodes) between-subject design was used (N = 122) to examine cognitive processes while learning with a concept map. No significant learning performance differences were found. Concepts maps with a low salience of map structure increased perceptions of disorientation. A serial mediation with learning performances as dependent variable revealed that the salience of the map structure is significantly associated with disorientation and extraneous cognitive load perceptions. By this, current attempts to measure extraneous cognitive load are questioned.