## 3 CB-Tree: A B-Tree Employing Cascade Memory Nodes
### Insert Operation  
The insert operation of CB-tree does not directly write the inserted record into the flash memory by storing it to the main memory. To defer the write operation on the flash memory, CB-tree employs the cascade memory nodes to insert a record and update the parent nodes. All the insert operations are carried out in the cascade memory nodes. To do this, node switching is performed in advance in the case that there is the flash node among the visited nodes. However, if the content of the memory node is not changed, the flash node will be simply loaded into a new memory node without node switching. This case is that the record is simply inserted or deleted in the leaf node. At this time, the previous memory node not to be changed is just removed from the main memory.  
Figure 6 shows an example of the insert operation in the CB-tree where three memory nodes (A, B, and E) and two flash nodes (C and D) exist. When a record with key 35 is inserted, nodes A, B, and E are traversed for the insertion. Since all the visited nodes A, B, and E, are in the cascade memory nodes, the record with key 35 is inserted into the memory node without invoking any flash operations.  
However, if there is at least one flash node among the visited nodes, node switching occurs between the visited flash node and the memory node at the same level. If a record with key 25 is also inserted after inserting the record with key 35, nodes A, B, and D are traversed for the insertion. Since leaf node D is not the memory node, node switching occurs between leaf node D and leaf node E at the same level. That is, memory node E is flushed from the main memory to the flash memory and flash node D is loaded into a new memory node D'. After node switching, the record with key 25 is inserted into leaf node D' that is a new memory node. In this example, two record insertions with keys 35 and 25 are completed in one write operation.  
Figure 7 shows the pseudo-code of the insert operation. Lines 2-12 describe the process of node switching during the tree traversal to find the target leaf node for the record insertion with a specific key (_key_). In lines 2-4, the insert algorithm identifies the node type of the current visiting node while traversing. If the current visiting node CurrentNode is a flash node, CurrentNode is loaded into the main memory as a new memory node. In order to reduce the number of write operations on the flash memory, the old memory node tempNode is written into the flash memory only if its content is changed in lines 7-8. In other words, every memory node does not have to be written into the flash memory if its content is same to the already stored node in the flash memory. Line 13 examines  
Figure 6: Example of the insert operation.  
whether the leaf node is full. In lines 14-21, if the leaf node is full, it checks the key sequences of the leaf node. If the key sequences are sequential, the leaf memory node is directly flushed from the main memory to the flash memory. An empty node is assigned for a memory node and then the record with a key is inserted into the newly allocated memory node. Otherwise, the leaf node is split into two leaf nodes. The leaf node for inserting the record with a key is assigned as a new memory node and the rest of the leaf node is written into the flash memory as a flash node. The parent memory nodes are also updated similar to the insertion of leaf nodes.