## 4 System Analysis  
To estimate the performance of CB-tree, we analyze the behaviors of CB-tree and the B-tree. For ease of analysis, we assume the following:  
* There are enough free blocks to perform the insert, delete, and search operations without any garbage collection in the flash storage device because it is difficult to know how the flash storage device stores data internally. * The cost of the insert, delete, or search operation is calculated without any operation cost that occurs in the main memory. That is, we only consider the cost of the operations that take place in the flash memory. Figure 11: Example of flushing memory nodes. Table 2 summarizes the notation used in our analysis. The search operation of the B-tree requires the same number of the read operations as the tree height \(H\) because the target node with the desired record is always traversed from the root node to the leaf node. Therefore, we can obtain the cost of the search operation of the B-tree \(R_{B}\) as follows:  
\[R_{B}=C_{R}H \tag{1}\]  
Compared to the B-tree, the node split causes updating for the parent node is less performed in CB-tree. As a result, the tree height of CB-tree is equal or less than the B-tree but we assume that the height of CB-tree is the same as the height of the B-tree \(H\) for convenience of the analysis. Generally, the search operation of the CB-tree is also affected by the tree height because CB-tree traverses all paths from the root node to the leaf node for searching the desired record regardless of the node type. If the visited nodes are all the cascade memory nodes, there is no read operation on the flash memory. Otherwise, all the visited nodes except the root node are read on the flash memory. Therefore, in the worst case, we can obtain the cost of the search operation of the CB-tree \(R_{C}\) as follows:  
\[R_{C}=C_{R}(H-1) \tag{2}\]  
From (1  
In the worst case, the cost of the insert operation of CB-tree is much higher than that of the B-tree. However, in the real system, since most of the write patterns (about 80-90%) are sequential and most of the visited nodes are memory nodes, node switching rarely occurs in CB-tree. Therefore, we expected that the insert operation is faster than that of B-tree in the real system. In order to estimate the write performance for sequential data pattern, we suppose that n records are sequentially inserted in continuous key order and a node of the tree index structure can store maximum \(m\) entries. If \(n\) records are sequentially inserted in the B-tree, the total cost of the insert operations \(T_{B}\) is obtained as follows:  
\[T_{B}=n(C_{R}H+C_{W}) \tag{5}\]  
Furthermore, the B-tree requires additional write operations for the node split when the leaf node overflows. At this time, at least two write operations are invoked for storing a new split-leaf node and updating the parent node. For easy estimation, we suppose that updating the parent node is always performed from the leaf node to the root node. That is, the cost of updating the parent nodes is \(C_{W}H\). Since the half of the leaf node is always filled after splitting the leaf node if records are sequentially inserted, the leaf node is split whenever \(m\)/2 records are inserted. Therefore, in the case of the sequential insertions, we can obtain the total cost of the insert operations \(T_{B}\) as follows:  
\[T_{B}=n(C_{R}H+C_{W})+2n/m\cdot C_{W}H \tag{6}\]  
In CB-tree, when records are inserted in a sequential key order, the leaf node is not split. Also, the cost of the search operation to find a leaf node equals to _zero_ because the visited nodes are all the cascade memory nodes. At this time, the leaf memory node is directly written into the flash memory whenever \(m\) records are inserted.