## 3 CB-Tree: A B-Tree Employing Cascade Memory Nodes
### Insert Operation in the Case of Sequential Insertions  
Figure 8 shows an example of record insertions with sequential key values in the general B-tree. There are leaf node C with continuous keys 5, 6, 7, and 8. If a record with key 9 is inserted into the B-tree, leaf node C will be split into two nodes due to the node overflow. In this case, three write operations on the flash memory are performed for storing leaf nodes C1, C2, and root node A'. Therefore, frequent node splits result in performance degradation in the flash storage device. In particular, space waste increases in split-leaf nodes (C1 and C2) with continuous keys. For example, leaf node C1 with keys 5 and 6 is flushed into the flash storage device even though there is empty space for more keys. This leads poor space utilization. To address these problems for splitting the leaf node, CB-tree does not split the leaf node when the leaf node with continuous key values overflows. Instead, it flushes only the leaf node fully filled with sequential key values into flash memory and maintains the rest inserted key values in a newly allocated leaf memory node. This approach improves the space utilization and reduces the write operations on the flash storage device.  
Figure 8: Sequential insertions of the B-Tree.  
Figure 7: Pseudo code of the insert operation.  
Figure 9 shows an example of sequential insertions. When records are sequentially inserted in following key sequences: 30, 31, 32, and 33, the records are inserted into memory node E. If a record with key 34 is inserted, leaf node E will overflow and be split in the B-tree but the leaf node will not be split in CB-tree. Since there are only sequential key values in memory node E, memory node E is directly flushed from the main memory to the flash memory before the record with key 34 is inserted. Then, the record with key 34 is inserted into new memory node F. In this example, five record insertions are performed in one write operation on the flash memory and flash node E is fully filled.  
As a result, CB-tree improves write throughput and page utilization by slightly changing the property of the original B-tree where all leaf nodes have between \(\lceil(n-1)/2\rceil\) and \((n-1)\) key values (\(n\) is the degree of a B-tree).  
The benefit in two aspects can be gained from direct flushing the leaf node without node splits. In terms of performance, the number of write operations on the flash memory decreases. Most files and records are sequentially written in the general file systems and the conventional database system [46]. If a large amount of records with sequential key values are inserted, our approach has more performance gains. Since the leaf memory node is almost empty after flushing the leaf node in the case of sequential insertions, large sequential insertions are performed in the leaf memory node without node splits and node switching. Consequently, the write performance increases because many write operations are deferred on flash memory. In terms of page usage, the page utilization of the leaf node increases because the entire space of the flash page is fully filled with records of the leaf node, whereas only half of the flash page is filled if splitting the leaf node.