## 5 Performance Evaluation
### Comparison with Structure-Modified B-Trees
Although the number of write operations increases, the overall performance is better than the other B-tree index structures because the number of the read operations in CB-tree is much smaller than the other index structure. This experimental result is shown in the following Figure 17.  
Figure 17 shows the creation time in structure-modified B-trees. Their patterns of results are similar to the number of flash operations in Figure 16. As the ratio goes to 100% (in Figure 17c), Wandering tree quickly builds the index structure because less node splits are performed than the case of the 0% ratio (in Figure 17a). However, regardless of the ratio, Wandering tree is much slower than the  
Figure 17: Creation time in structure-modified B-trees. other trees because it stores all the updated parent nodes when inserting a record. As you can see the results in Figure 16, \(\upmu\)*-tree performs more flash operations than dIPL B+-tree and LSB-tree. In \(\upmu\)*-tree, the number of read operations is much more than the number of write operations. Unusually, the total creation times of these three trees in various ratios are almost similar because the read operation is faster than the other flash operations. As depicted in Figure 17a, CB-tree is quickly built compared to the other B-trees because no read and erase operations are invoked on the flash memory. Although CB-tree is slowly built because much node switching occurs between the memory node and the flash node in CB-tree as the ratio increases, its creation performance is always faster than any other tree. Additionally, even though CB-tree performs log writing, its performance is still 22.6-41.8% better than the other structure-modified B-trees because of only the number of write operations for the logs increases. From the results of Figure 17a-c, we confirm that CB-tree quickly builds the index structure compared to the other structure-modified B-trees. Figure 18 shows the average search time when finding a record in the index structure already built in Figure 15. In all ratios, Wandering tree finds a record in a similar time because its search operation is affected by only the tree height. As shown in Figure 18a, dIPL B+tree and LSB-tree find a record similar to Wandering tree because records rarely exist in the log area in the case of the 0% ratio. However, as depicted in Figure 18c, the search performance decreases as the ratio goes to 100% because searching is invoked in two places the log area and the data area. Although the search operation of the \(\upmu\)*-tree is very slow because of the frequent leaf node splits causing a rapid increment of the tree height, its search performance is uniform in all ratios. CB-tree quickly finds a record compared to the other B-trees because some internal nodes stayed in the memory nodes. Through the experiment, we confirmed that CB-tree more quickly finds a record compared to the other structure-modified B-trees. Figure 18: Average search time in structure-modified B-trees. As shown in Table 6, we measured the number of allocated pages on the flash memory when the index structures are built. Based on Wandering tree, dIPL B+-tree and \(\mu^{*}\)-tree allocates many pages on the flash memory. The reason is that dIPL B+-tree needs the log area to write the changes of the leaf node and the \(\mu^{*}\)-tree needs many pages due to its unique page layout. As the ratio goes to 0%, LSB-tree and CB-tree need fewer pages than any other B-trees because they do not perform the node split in the case of sequential insertions. Through the results, we found that CB-tree requires fewer pages to create the index structure compared to the other structure-modified B-trees.