Implementation issue of lazy recovery mechanism

[SeKwonLee]

Current implementation for insertion operation cannot correctly handle crash-inconsistent data after crash occurs in the middle of node split. Below algorithm shows the current insertion implementation provided by this repository.

1. Traversing down tree with lock-free search until reaching leaf node.
   i) If it is found that the next node's smallest key is smaller than the requested key during traversing, thread moves to right sibling node, and then continues to traverse tree.
2. Acquiring the lock of the found leaf node and inserting new key
   i) Before inserting new key, check again the next leaf node's smallest key. If the smallest key in the next node is larger than the new key, the thread unlocks current locked leaf node, and then continues to do insertion from the next leaf node.

The key problem is that this insertion algorithm does not involve any recovery mechanism even if writer thread finds that the smallest key of next sibling node is larger than new key. If we use this algorithm as-is, the following problem can occur after system crash occurs in the middle of node split.

1. Initial tree has only one leaf node (1, 5, 9, 15) where the maximum number of entries is four.
2. Writer thread tries to split first to insert new key 20.
3. (1, 5, 9, 15) is split to (1, 5) --> (9, 15)
4. **System crash** occurs before allocating new root and inserting middle key into it.

**System resume**

5. Following writers insert new keys 20, 30, and 40. When inserting 40, node split is conducted, and then allocating new root node.
6. After previous insertions, the final tree structure is formed like below.
                    (20)
                  /      \
   (1, 5)-->(9, 15)-->(20, 30, 40)
7. Reader thread tries to search key 5, but it will return failure even if key 5 is valid in this tree structure.

The lazy recovery mechanism, originally proposed in FAST'18 paper, performs recovery whenever a thread finds the smallest key in the right side node is bigger than the requested key. It seems the current implementation choice is because of performance. However, it would be expected that performance become somewhat different if the implementation is changed to correctly address lazy recovery mechanism.