Strictly speaking you can store some energy without the air gap but the permeability of magnetic materials such as ferrite is so much higher than free space that energy storage is negligible in the magnetic material. The gap does not have to be air just non-magnetic and it can be distributed into a number separate gaps, including microscopic ones.
