## 1 Introduction  
Flash storage devices have been widely used in diverse application areas from small embedded systems to large scale servers. There are various kinds of flash storage devices such as an embedded multimedia card (eMMC), a solid-state drive (SSD), and an all-flash array. Compared to the traditional magnetic disk drive, the flash storage device has many advantages like fast access speed, low power consumption, and high reliability [1; 2; 3]. The flash storage device inherits the distinctive characteristics of NAND flash memory because it is composed of a number of NAND flash arrays. A flash array consists of many blocks with a fixed number of pages each. Differently with the magnetic disk drive, the flash memory requires an erase operation before data is written in the same physical address because it cannot overwrite data in-place. Furthermore, the erase operation is performed in a block unit and so it is much slower than the read or write operations that are done in a page unit [4]. The flash memory cannot be directly deployed as a storage device in the conventional host system by itself due to the aforementioned physical characteristics. Therefore, many vendors of the flash storage device have adopted an intermediate software layer, which is called a flash translation layer (FTL), between the host systems and the flash memory. The key role of the FTL is to redirect each write request from the host to an empty flash page that has already been erased in advance, thus overcomingthe limitation of in-place updates. In the internal architecture of the flash storage device, its controller performs FTL functionality that makes the flash memory work as a block device like the magnetic disk drive [5; 6; 7]. A B-tree [8; 9] index structure is widely used in conventional file systems (e.g., ReiserFS [10], XFS [11], Btrfs [12]) and database systems (e.g., PostgreSQL [13], MySQL [14], SQLite [15]) because of its ease of construction and retrieval performance. The B-tree intensively overwrites data into the same node so as to keep the balance of the tree height. Therefore, severe performance degradation occurs when the B-tree index structure is deployed in the flash storage device although the FTL provides an efficient mapping algorithm. In order to enhance the performance of the B-tree on flash devices, various B-tree index structures have been proposed for flash memory. Flash-aware B-tree index structures are classified into two categories. The first group has B-trees that employ the memory buffer to improve the write throughput. These buffer-based B-trees are much faster than another group, but they suffer from the high cost of maintaining the memory buffer and risk of data loss in the case of a sudden power failure. The second group's B-trees are the variations that modify node structure to avoid in-place updates. These structure-modified B-trees have more reliable features and also need small memory resources than buffer-based B-trees. However, their write performance is poor because they invoke many write operations. In this paper, a novel B-tree index structure is proposed for the flash storage device in order to improve the overall performance with small memory resources and page utilization. For reducing the number of write operations, it keeps the modified B-tree nodes by key insertions in the main memory until the batch writes are performed in a cascade manner. Additionally, the proposed B-tree index structure does not split leaf nodes so as to avoid additional write operations for the node split and store more keys in the leaf node when records with continuous key values are sequentially inserted. Through mathematical analysis and various experimental results, we show that the proposed B-tree index structure always yields better performance than existing works. The rest of this paper is organized as follows. Section 2 reviews flash-aware index structures and discuss the drawbacks of the related works. Section 3 describes the proposed B-tree index structure.