## 5 Performance Evaluation
### Comparison with Buffer-Based B-Trees  
We first evaluated the performance of buffer-based B-trees for large scale file systems and database systems. To estimate realistic values, we used traces collected by SNIA (Advancing Storage and Information Technology) [48]. Table 5 shows the number of I/O operations extracted in traces. MSR Cambridge data are the 1-week block I/O traces collected in the enterprise server of Microsoft Research in Cambridge. Exchange data are traces collected for an Exchange Server for a duration of 24 h. The TPC-C and TPC-E data are TPC-C and TPC-E benchmark traces collected at Microsoft. Trace patterns of MSR Cambridge and TPC-C benchmark show the number of write requests similar to the number of read requests. Exchange server invokes many write requests due to sending many e-mails whereas the TPC-E benchmark writes data once and reads data many times. To compare performances among buffer-based B-trees, we measured creation time and retrieval time by performing write requests and read requests from the above real traces on an MLC flash SSD. The original disk-based B-tree is used as a base algorithm without any memory buffer. For fair evaluation, the optimal buffer size is first obtained by increasing the page size. When the buffer size equals eight pages, the creation time shows the best performance. As a result, the buffer size is fixed to eight pages. Even though the buffer size of CB-tree dynamically increases as the tree height increases, its buffer size does not exceed the size of four pages because the heights of index structures created from the above traces become at most four. Figure 13 shows the creation time when performing each write requests as shown in Table 5. Overall, IBSF and CB-tree are quickly built compared to the other index structure because they do not reorder the records in the memory buffer. In the cases of Figure 13a,c, CB-tree is built 27.6-36.4% faster than IBSF. Since their write requests show sequential patterns, the CB-tree reduces a large amount of node splits for the leaf node. Although the TPC-E benchmark has a more random pattern than the TPC-C benchmark does, the CB-tree is built 22.8% faster compared to IBSF because IBSF requires many seeks to find records to be inserted into the same logical node in the memory buffer. \begin{table}
\begin{tabular}{c c c} \hline \hline
**I/O Type** & **SSD Product** & **OpenSSD** \\ \hline Sequential Read & 225 MB/s & 66.5 MB/s \\ Sequential Write & 66.5 MB/s & 22 MB/s \\ Random Read (4 KB) & 16.5 MB/s & 10.5 MB/s \\ Random Write (4 KB) & 20 MB/s & 2.5 MB/s \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Performance of flash storage devices. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Server** & **Write Requests** & **Read Requests** \\ \hline MSR Cambridge & 1,877,535 & 1,625,346 \\ Exchange & 3,921,312 & 1,789,471 \\ TPC-C & 1,263,387 & 1,836,124 \\ TPC-E & 123,562 & 1,313,596 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: The number of operation requests in each trace. Most of buffer-based B-trees including IBSF reduce the number of write operations for leaf node updates by simply employing a write buffer. However, since they do not consider flash operations for updating parent nodes and merging or splitting leaf nodes, the performance degradation may occur. In CB-tree, we exploit cascade memory nodes to avoid many updates for parent nodes and node splits for the leaf node in the case of sequential insertions. As a result, we confirmed that CB-tree quickly builds its index structure compared to the other buffer-based B-trees. Figure 14 shows the total retrieval time when the trees perform each read request as shown in Table 5. The B-tree without any buffer performs the same number of read operations as its tree height in every read request. Since LU-tree, IBSF, and AS-tree store some records in the main memory, these records are also used in retrieval operations. Before traversing nodes to find a record, they first search the record in the buffer and then visits the nodes in the flash memory.