## 5 Performance Evaluation
### Comparison with Structure-Modified B-Trees  
For evaluating the performances of structure-modified B-trees, we used OpenSSD platform for adopting the custom mapping algorithm (i.e., FTL) because structure-modified B-trees need direct mapping to a physical address. In addition, OpenSSD can count the internal flash operations (read/write/erase operation). In order to compare the creation time of structure-modified B-trees, we measured the number of the read/write/erase operations and the total elapsed time by inserting 50,000 records with various key sequence ratio. If the ratio of key sequences is equal to 0%, the records with keys that are sorted in ascending order are sequentially inserted. In contrast, if the ratio is equal to 100%, the records with the key that are randomly generated are inserted. Figure 16 shows the counts of flash operations when records are inserted. The wandering tree is used as a basic B-tree for the flash memory. In these figures, B-tree, dIPL B, and CB(log) mean Wandering-tree, dIPL B+-tree, and CB-tree with log writes, respectively. Except for CB-tree, the other trees require a similar number of the read operations in every case because finding the leaf node to insert data affected by the tree height. However, since sometimes read operations are not performed to find the leaf node for the insertion according to the ratio of key sequences, CB-tree needs less read operations than the other trees. Figure 15: The number of flash operations in buffer-based B-Trees. As depicted in Figure (a)a, the search operations on the flash memory are not invoked in CB-tree because the visited nodes for inserting records are all memory nodes. Erase operations on the flash memory are not also invoked because fewer pages are used to store only the memory nodes compared to the other trees. Also, fewer write operations are performed because the nodes in the CB-tree are written in the batch process only if the leaf memory node becomes full and the other trees always write a record in the flash memory whenever the record is inserted. Therefore, in the case of ratio 0%, the CB-tree more quickly creates the index structure than any other tree. Figure (b)b shows the operation counts in the case of the 50% ratio. The operation counts in Wandering tree are similar to the case of 0% ratio. The operation counts in dIPL B+tree, \(\upmu\)*-tree, LSB-tree, and CB-tree trees increases compared to the case of ratio 0%. Interestingly, in \(\upmu\)*-tree, the number of the read operations increases but the number of write operations and the number of erase operations decrease because fewer node splits are invoked by employing many new pages for inserting records. In the dIPL B+-tree and LSB-tree, since more complicated merges between the log area and the data area occur, more flash operations are performed. CB-tree also needs more flash operations to swap the nodes between the memory node and the flash node. Even though more flash operations are invoked in the CB-tree, the number of flash operations in the CB-tree is much less than the other trees. Similarly, as the ratio goes to 100%, the flash operation counts increase in every tree except the \(\upmu\)*-tree as depicted in Figure (c)c. Since the \(\upmu\)*-tree uses more pages to insert records without node splits, its operation counts are reduced. From these experiments, we confirmed that CB-tree efficiently reduces the number of write operations by keeping the updated records in the memory node. Figure 16: The number of flash operations in Structure-modified B-Trees. For evaluating the overhead of the log writing, we additionally measured the operation counts with the log writing. Through the results of Figure 16a-c, the number of its write operations increases as the number of inserted records increases since additional write operations for the logs are performed in the logging process. As the ratio goes to 100%, the number of flash operations of CB-tree and CB(log) becomes similar due to node switching.