NAND flash memory has become the major persistent data storage medium for mobile and embedded devices (e.g. cell phones, USB Disk Drive, mp3 player) because of its low access latency, low power consumption, and high shock resistance. On the other hand, due to its erase-before-write limitation, it is also known that flash memory exhibits poor write performance especially when write operations are requested in a random order. Random write is a fairly common access pattern in many database applications. An index structure is an essential component in database applications to search for or locate data objects from a large database, but it tends to make data access pattern more random.