The Aubry-Andre model is a one-dimensional lattice model for quasicrystals with localized and delocalized phases. At the localization transition point, the system displays fractal spectrum, which relates to the Hofstadter butterfly. In this work, we uncover the exact self-similarity structures in the energy spectrum. We separate the fractal structures into two parts: the fractal filling positions of gaps and the scaling of gap sizes. We show that the fractal fillings emerge for a certain type of incommensurate periodicity regardless of potential strength. However, the power-law scaling of gap sizes is characteristic for general incommensurability at the critical point of the model.