## 3 CB-Tree: A B-Tree Employing Cascade Memory Nodes
### Overview  
CB-tree classifies the nodes into memory node for performance and flash node for reliability. The memory node is a node that stays in the main memory, and the flash node is a node to be stored in the flash memory. CB-tree employs only one memory node for each level of the B-tree to reduce the usage of memory resources and the risk of data loss. The more memory nodes there are, the better the performance. However, the usage of memory resources and the risk of data loss may also increase. Therefore, CB-tree maintained only one memory node for each level of the B-tree and consequentially the number of memory nodes is equal to the height of the B-tree. In this paper, all the memory nodes from the leaf node to the root node are called cascade memory nodes.  
When a record is inserted or deleted in the B-tree, several nodes of the B-tree are traversed from the root node to the leaf node for finding the target leaf node. The insertions and deletions are performed in the target leaf node after arriving at the leaf level. If the target leaf node overflows or underflows, the visited parent nodes during traversing will be updated. These parent updates invoke many internal read, write, and erase operations on the flash storage device. Since, in CB-tree, all the insert and deletion operations are completed in only the cascade memory nodes, the number of read, write, and erase operations on flash devices may be reduced. Only node switching invokes the read and write operations for the flash storage device. If a flash node is visited for inserting or deleting a record, node switching occurs between the current visiting flash memory and the memory node existing at the same level. That is, the content of the memory node at the same level is flushed to the flash memory and then the content of currently visited flash node is loaded into a new memory node. That is a basic process of node switching that will be explained in Section 3.2 for more details.  
When a record is inserted, some nodes from the root node to the leaf node are visited to insert the record. If the types of all the visited nodes are all the memory nodes, the write operations on the flash memory will not be invoked because the insert operation is performed only in the main memory. If not so, node switching will happen.  
Figure 5 illustrates the overview of CB-tree. There are six leaf nodes and four parent nodes including the root node. In this example, node B, C, E, F, G, H, and I are flash nodes and nodes A, D, and J are memory nodes. Therefore, only seven flash nodes are stored in flash memory. If a record insertion occurs in leaf node J, root node A, internal node D, and leaf node J will be visited. Since the visited nodes are all the memory nodes, the insert operation is performed in the cascade memory nodes without node switching. Therefore, this insertion for leaf node J does not invoke any operations on the flash memory.  
Whereas, if a record is inserted into leaf node H, root node A, internal node C, and leaf node H will be visited. Since nodes C and H are flash nodes, two nodes are swapped for the current memory nodes D and J at the same levels, respectively. In other words, memory nodes D and J are flushed from the main memory to the flash memory and then flash nodes C and H are loaded as new memory nodes in the main memory.  
Figure 5: Overview of CB-Tree.  
If the CB-tree is built by inserting records with random key values, its performance will decrease because node switching frequently occurs. On the other hand, if records are sequentially inserted, node switching will rarely occur because many record insertions are performed in the memory node. In conventional file systems, they have about 80-90% sequential patterns among the write patterns [43; 44]. The access pattern of multimedia systems also has a sequential write pattern [45]. Therefore, when the CB-tree is built with realistic data in the practical host system, its performance may not decrease because node switching is rarely invoked.