Column-store databases feature a faster data reading speed compared with traditional row-based databases. However, optimizing write operations in a column-store database is a well-known challenge. Most existing works on write performance optimization focus on main-memory column-store databases. In this work, we extend the research on column-store databases in the Map-Reduce environment. We propose a data storage format called Time stamped Binary Association Table (or TBAT) without the need of global indexing. Based on TBAT, a new update method, called Asynchronous Map-Only Update (or AMO Update), is designed to replace the traditional update. A significant improvement in speed performance is shown in experiments when comparing the AMO update with the traditional update.