## 2 Background and Related Work
### Structured-Modified B-Trees  
Structure-modified B-Trees change the node structures to avoid in-place updates. They are designed to handle the physical address because the early embedded system equips the raw flash memory without the FTL. Figure 4 shows a brief process of how structure-modified B-trees store the inserted records to the flash memory. In this example, the logical B-tree is built with six leaf nodes and four parent nodes including root node A. Assume that a node of the B-tree is mapped on a page on the flash memory.  
In flash file system JFFS3 [34], the wandering tree is the first B-tree index structure that considers the characteristics of the flash memory. In order to avoid the in-place update, the wandering tree stores all the updated nodes into empty pages on the flash memory when inserting a record. As shown in Figure 3(a), lead node J, parent node D, and root node A are written into new empty pages, respectively,  
Figure 4: Structure-modified B-Trees for flash memory.  
when inserting a record into leaf node J. As a result, it does not perform many erase operations caused by in-place updates, but it still requires many read/write operations for updating parent nodes.  
In order to reduce the additional operations for updating parent nodes, \(\mu\)-tree [35] and \(\mu^{*}\)-tree [36] write all the updated nodes into a single page on the flash memory. As shown in Figure 4b, \(\mu\)-tree writes updated leaf node J' and its parent nodes (nodes D and A) into an empty page on the flash memory when inserting a record into leaf node J. To do this, \(\mu\)-tree divides a page into several partitions in fixed-size. \(\mu^{*}\)-tree dynamically assigns the size of the leaf node according to its page state for improving the page utilization. In \(\mu\)-tree and \(\mu^{*}\)-tree, node splits frequently occur and the tree height increases rapidly because the sizes of leaf nodes are less than that of the original node for the B-tree. This feature causes severe performance degradation when building the index structure.  
IPL B+-tree [37] defers updating the parent nodes by storing only the changed records as logs. As shown in Figure 4c, IPL B+-tree divides a flash block into two areas: a data area that stores tree nodes and a log area that stores inserted, deleted, and updated logs corresponding to the data area. The size of the log area is fixed based on IPL [38]. In contrast to the IPL B+-tree, dIPL B+-tree [39] dynamically assigns the number of log pages on the block in order to efficiently use the log pages. If a record related to leaf node J is inserted, the record will be temporarily stored into the log block. When the log area becomes full, the data area and the log area are merged. This merge operation invokes many read, write, and erase operations on the flash memory.  
Similar to the IPL B+-tree, LA-tree [40], LSB-tree [41], and BbMVBT [42] also store all nodes to be updated into the temporary area on the flash memory for avoiding in-place updates. The retrieval performance of these index structures that employ log area is worse than that of the B-tree due to the traversal of the log areas.  
Most structure-modified B-trees guarantee high reliability because they directly store all updated records into the flash memory. However, they require additional operations such as parent updates and merge operations according to their structures.  
Table 1 shows the characteristics of the buffer-based B-tree and the structure-modified B-tree in terms of performance, reliability, and memory usage. It is necessary to develop a novel B-tree index structure that has the advantages of two B-trees such as fast performance, high reliability, and low memory usage.