Project2_Milestone1_2

Detail flow of the structure modification

(각 함수들의 모든 call path는 항목 참조)

Split

1. insert 함수에서
   • 입력받은 key와 중복된 key가 tree에 이미 존재하지 않고,
   • tree가 비어있지 않으며,
   • tree에 있는, 입력받은 key를 포함하는 범위의 leaf node가 여유 공간을 가지고 있지 않을 경우,
   • insert_into_leaf_after_splitting 함수를 call하여 해당 leaf node의 분할을 동반한 삽입을 수행한다. 이렇게 될 경우, Split(분할)이 수행된다. 그 수행 과정은 아래와 같다.
2. insert_into_leaf_after_splitting 함수에서
   • 임시 변수들로, 기본값보다 order가 1개 큰 1개 leaf node와 유사한 형태를 만든다.
   • leaf node에 존재하는 record와 key들을 임시 변수에 복사하되, 입력받은 record가 삽입될 위치를 비우고 복사한다.
   • 입력받은 record 포인터와 key값을 비워둔 위치에 삽입한다. 이렇게 하면, 기본값보다 order가 1개 큰 유사 node에 record/key가 꽉 찬 형태가 된다.
   • 임시 변수로부터 분할할 왼쪽 절반 record와 key들을 leaf node로 복사한다.
   • 임시 변수로부터 분할할 오른쪽 절반 record와 key들을 새로 생성한 leaf node로 복사한다.
   • 기존 leaf node와 새로 생성한 leaf node가 가지는 값들을 변경된 사항에 적합하게 최신화한다.
   • insert_into_parent 함수를 call하여 새로 생성한 leaf node를 부모 node에 삽입한다.
3. insert_into_parent 함수에서
   1. 부모 node가 존재하지 않을 경우, 즉 root node가 분할된 상태일 경우 insert_into_new_root 함수를 call하여 새로운 root node를 생성하고 분할된 2개 node를 그에 삽입한다.
   2. 부모 node에 새로 생성한 leaf node가 삽입될 여유 공간이 있을 경우, insert_into_node 함수를 call하여 삽입을 수행한다.
   3. 부모 node에 새로 생성한 leaf node가 삽입될 여유 공간이 없을 경우, insert_into_node_after_splitting 함수를 call 하여 부모 node의 분할을 동반한 삽입을 수행한다. 즉 Split이 추가적으로 수행된다. 또한, insert_into_node_after_splitting 함수는 위의 과정 2 insert_into_leaf_after_splitting 함수와는 달리 leaf node가 아닌 internal node를 분할하지만, 유사하게 동작하며, 따라서 Split이 추가적/반복적으로 발생할 수 있다.

Merge

1. delete 함수에서
   • 입력받은 key를 가지는 record가 존재할 경우,
   • 해당 record를 삭제하기 위해 delete_entry 함수를 call한다.
2. delete_entry 함수에서
   • 해당 key/record를 가지는 node가 root node가 아니며,
   • 해당 key/record를 삭제한 후 해당 node의 key 개수가 현재 order에 따른 최소 key 개수 미만이고,
   • 병합해도 최대 key 개수를 넘지 않는 형제 노드를 찾았을 경우,
   • coalesce_nodes 함수를 call한다. 이렇게 될 경우, Merge(병합)가 수행된다. 그 수행 과정은 아래와 같다.
3. coalesce_nodes 함수에서
   • 두 node가 leaf node인지 확인한다.
     1. 두 node가 leaf node가 아닐 경우, 두 node 사이의 key를 왼쪽 node가 가진 key들 제일 끝에 삽입하고, 이후 오른쪽 노드의 key와 포인터들을 왼쪽 node로 옮긴다. 왼쪽 node가 가지게 된 포인터들이 모두 왼쪽 node를 부모 node로 가리키도록 최신화한다.
     2. 두 node가 leaf node일 경우, 오른쪽 node의 key와 포인터들을 왼쪽 node로 옮긴다. 오른쪽 node가 다음 node로 가리키던 node를 왼쪽 node가 다음 node로 가리키도록 최신화한다.
   • delete_entry 함수를 call하여 오른쪽 node를 삭제하도록 한다. record를 삭제하는 위의 과정 2와는 달리 node를 삭제하지만, 유사하게 동작하며, 따라서 Merge가 추가적/반복적으로 발생할 수 있다.
   • 오른쪽 node와 그 멤버 변수들을 할당 해제한다.