MEMS-based storage systems have recently generated significant interest due to their potential to be faster and more efficient than disks, while providing the non-volatility property. Designing data layouts for these devices is a challenging, important and interesting problem. In this paper, we explore various ways of placing a database on a MEMS-based storage architecture. Three novel data layouts are proposed after considering the MEMS device characteristics and the access patterns arising from queries. We then design the access methodology for each layout and evaluate these layouts based on their respective I/O service times. Overall, our results were able to identify the intricacies of placing data on a MEMS-based storage and also ascertain the large potential of MEMS-based devices for databases.