## 3 CB-Tree: A B-Tree Employing Cascade Memory Nodes
### Memory Node Management  
To minimize the overhead of memory resources, the number of entries in a memory node is dynamically allocated in the main memory by growing or shrinking the memory size. Even though the memory node can also have a maximum number of entries in a node, the size of the memory node is assigned to fit the number of key values if there are empty entries in the memory node. CB-tree does not assign the memory space for empty entries in advance to avoid the waste of the unnecessary memory space. When inserting a record, the CB-tree assigns an index entry to store the inserting record in the main memory and then links the newly allocated index entry to the end of the leaf memory node. After connecting the index entry, the contents of memory node and index entry are sorted. Figure 10 shows the structure of the physical storage in a part of CB-tree where three memory nodes (A, B, and E) and two flash nodes (C and D) exist. If a record with key 25 is inserted, flash node D will be loaded as a new memory node (D\({}^{\prime}\)) and flash node D and the memory node E will be flushed from the main memory. Although node E, at the first, was the memory node, it become the flash node after being flushed. After node switching, the record with key 25 is inserted into D\({}^{\prime}\) but there is no main memory space to insert the record. Therefore, CB-tree newly assigns an index entry with key 25 and then links it to the end of memory node D\({}^{\prime}\) as depicted in the middle of Figure 10. Since the key value of the inserted records is the biggest in leaf node D\({}^{\prime}\), it is unnecessary to sort the key values in leaf node D\({}^{\prime}\). After inserting the record, the total size of the allocated memory becomes the size of eight entries by increasing its size. To prevent the data loss in the case of a sudden power failure, all the cascade memory nodes of CB-tree should be flushed from the main memory to the flash memory periodically. Basically, on a large scale server system, which is rarely turned off and focused on high performance, all the memory nodes are flushed only if the size of the root node increases. As shown in Figure 11, for example, if inserting a record into leaf node E, the root node will increase. At this, all the memory nodes (nodes A, B, and E) are stored into the flash memory before increasing the root node. Figure 10: Structure of the physical storage in CB-tree. In embedded systems that are frequently turned off, a more robust logging technique is required. CB-tree assigns log areas in the main memory and the flash memory to maintain the inserted and deleted records for the power-off recovery. To write the changed logs in one write operation on the flash memory, the maximum size of the log area cannot exceed the size of a page on the flash memory. Before flushing memory nodes, it always stores all the inserted and deleted records (including a key value, a record address, and an operation type) into log areas in the main memory and flash memory in FIFO order. In order to avoid reading the previous log data stored in the flash memory when writing the logs, CB-tree stores logs in both the main memory and flash memory. Therefore, the CB-tree only refers the log areas in the main memory when recovering its index structure. When the log area becomes full, all the cascade memory nodes are flushed into flash memory and then all the logs stored in both areas are removed. For recovering the index structure, CB-tree first finds the final flushed root node and the content of the log area stored in the flash memory. The found root node is used for a new root memory node and then all the records in the log area are inserted and deleted in stored order. For example, assume that the sudden power failure occurs after flushing all the cascades nodes (nodes A, B, and E as depicted in Figure 11) and inserting three records (following key sequence: 7, 1, and 9). There are three records, which are stored in the inserted order, of the log area in the flash memory.