MEMS-based storage is an emerging storage media that has several attractive features such as high-bandwidth, low-power consumption, and low cost. However, MEMS-based storage has vastly different physical characteristics compared to a traditional disk. First, MEMS-based storage has thousands of heads that can be activated simultaneously. Second, the media of MEMS-based storage is a square structure which is different from the rotation-based platter structure of disks. Third, the size of a sector in MEMS-based storage is smaller than 512 bytes of a conventional logical block. In this paper, we present a new address mapping scheme for MEMS storage that makes use of the aforementioned characteristics. This new scheme exploits the complete parallel feature of MEMS-based storage as well as the characteristics of the two dimensional square structure. Simulation studies show that the new scheme improves the performance of MEMS storage significantly by exploiting the high parallelism of MEMS storage.