Project2_milestone1

1.possible call path of the insert/delete operation.

1)Call path of insert operation

(1) 삽입할려는 키가 원래 존재하는 것인지 판단

• 이미 존재하는 경우 : 중복을 허용하지 않기 때문에 그대로 root를 반환해준다

• 존재하지 않는 경우 : 키를 담을 레코드를 생성한 후 그 레코드 포인터를 저장해둔다

(2) 트리가 존재하는 지 판단

• 트리가 존재하는 경우 : 키가 들어갈 리프노드를 가져온 후 다음 과정으로 넘어간다.(find_leaf함수 호출)

• 트리가 존재하지 않는 경우 : 새 루트를 생성해준다 (start_new_tree함수 호출)

(3) (가져온 리프노드에)키를 담을 공간이 이미 존재하는지 판단

• 공간이 없는 경우 : 삽입 후 split을 해준다(insert_into_leaf_after_splitting함수 호출)

• 공간이 있는 경우 : 키를 삽입해준다(insert_into_leaf함수 호출)

2)Call path of delete operation

(1) 키를 가진 레코드와 노드가 있는지 판단

• 없는 경우 : 그냥 root를 반환한다.

• 있는 경우 : 삭제를 위해 delete_entry함수 호출

(2) 키를 가진 노드가 루트인지 판단 (delete_entry 내부)

• 루트인 경우 : adjust_root함수를 호출하여 삭제를 끝낸 루트노드가 빈 루트인지 비어있지 않은 루트인지 판별한다.

비어있지 않은 루트일 경우 다른 수정없이 루트를 반환한다.

빈 루트인데 자식이 존재하는 경우는 자식하나를 루트로 올려주고 자식이 존재하지 않는 경우에는 완전히 빈 트리임을 의미하므로 NULL을 반환한다.

• 루트가 아닌 경우 : 다음 과정으로 넘어간다.

(3) 삭제한 이후 트리를 유지할 조건을 만족하는지 판단

• 만족하는 경우(합친 후의 크기가 최소크기 이상인 경우) : 수정할 필요가 없으므로 바로 루트를 반환한다.

• 만족하지 못하는 경우 : 합쳐야 하므로 아래 과정을 진행한다.

(4) 합쳤을 때 용량을 초과하는지 판단

• 합칠 수 있는 경우 : coalesce_nodes함수를 호출한다

• 초과하여 합칠 수 없는 경우 : redistribute_nodes 함수 호출을 통해 재분배한다.

2.Detail flow of the structure modification(split, merge).

1)Split - 삽입 후 용량 초과의 경우

(1) insert_into_leaf_after_splitting

• 함수 내부에서 새로 만들어질 리프노드와 임시공간노드를 생성해준다.

• 임시공간 노드에 삽입할 위치를 찾고 원래 레코드들과 새 레코드를 순서에 맞게 삽입한 후 분할지점을 정하여 원래 리프 노드와 새 리프노드에 쪼개서 넣어준다.

• 임시공간의 메모리를 해제시켜주고 새로 만들어준 리프노드를 원래의 노드와 연결해준다.

• 원래 리프노드에서 사라진 값들에 대한 조정과 새 리프노드의 부모설정을 해준다.

• 부모로 올려서 넣을 키를 선정한 후 해당 키 삽입을 위해 아래 함수를 호출한다.

(2) insert_into_parent

• 키를 삽입 해줄 부모가 존재하지 않아 새로 루트를 생성해줘야 하는 경우 : insert_into_new_root 함수 호출

• 키를 삽입한 부모 노드의 용량이 초과하지 않는 경우 : insert_into_node 함수 호출

• 키를 삽입한 부모 노드의 용량의 초과한 경우 : insert_into_node_after_splitting함수 호출

(3_1) insert_into_node

• 삽입할 위치를 확보하기 위해 한칸씩 밀어주는 작업을 한다.

• 빈 공간에 키와 포인터를 삽입해주고 root를 반환한다.

(3_2) insert_into_node_after_splitting

• split에 필요한 새 노드와 임시 노드를 생성해준다.

• 임시 노드에 원래 노드의 값들과 새로 넣을 값들을 순서에 맞게 넣어준다.

• 분할 지점을 설정하고 원래 노드와 새 노드에 쪼개서 넣어준다.

• 임시 노드를 비워준 후 새 노드와 원래 노드의 부모를 일치시키고 새 노드의 자식들의 부모를 재설정한다.

• 다시 부모로 올릴 키를 선정하고 insert_into_parent 함수 호출 (조건이 만족될 때까지 반복하게 됨)

2)Merge - 삭제 후 최소크기를 넘지 못한 경우

merge의 경우 두가지 방식이 존재한다. 너무 작아진 노드를 이웃과 합쳤을 때 용량이 초과된 경우 두 노드사이의 항목을 재분배(빌려오기)하는 redistribution과 용량이 맞아 수정이 조정이 필요없어 단순히 합병만 하는 coalescence이다.

(1) Coalescence

• 왼쪽 이웃노드를 받아오는데 현재 노드가 가장 왼쪽 노드일 경우 자신의 오른쪽 노드에 합친다.

• 리프 노드인 경우 : 이웃노드로 자신의 항목을 옮겨주고 이웃의 끝 포인터가 자신의 오른쪽 노드를 가리키게 설정해준다.

• 리프 노드가 아닌 경우 : 왼쪽 노드에 항목을 옮겨준 후 자신의 자식들의 부모를 이웃노드로 설정해준다.

• 해당 노드의 메모리를 정리해준다.

(2) Redistribution

• 왼쪽의 이웃 노드에게서 빌려오는 경우 : 이웃의 마지막 키와 포인터를 자신의 노드의 왼쪽끝으로 가져온다.

• 오른쪽의 이웃 노드에게서 빌려오는 경우 : 이웃의 처음 키와 포인터를 자신의 노드의 오른쪽 끝으로 가져온다.

• 이때 리프노드가 아니였을 경우 자식에 대한 재조정도 필요하다.

3.Designs or required changes for building on-disk b+ tree.

1)Page

• 기존의 b+ tree를 수정해서 on-disk b+ tree를 구현하기 위해서는 page에 대한 추가적인 작업이 필요하다.

• 필요한 페이지는 4가지로 header page,free page,leaf page,internal page이다.

• 구조체 정의를 통해 구현 가능하고 구조체 내부에 각 페이지에 필요한 헤더와 담아야하는 정보(아래 참조)들을 구현해두도록 한다.

• header page : 첫 free page의 위치, root page 위치, 데이터 파일에 존재하는 페이지 수

• free page : 다음 free page의 위치

• leaf page : page header(parent page,is leaf,key의 개수,right sibling page) ,record(key+value)

• internal page : page header(parent page,is leaf,key의 개수,자식 페이지들 중 첫 page의 number), key(8)+page number(8)

2)Insert

• pointer로 자식노드를 가르키던 게 페이지 넘버를 통해 위치가 가리켜지고 있기 때문에 이에 대한 수정이 필요하다

• 새 페이지가 필요할 경우 free page의 정보를 읽어와서 삽입한다.

• 매개변수에 페이지 번호도 추가로 넘겨주어야 한다.

• split이 일어날 경우 페이지 정보 갱신이 필요하다.

3)Delete

• 성능저하를 막기 위해 페이지 내의 모든 키가 삭제될 때까지 merge를 미루는 delayed merge에 대한 작업이 필요하다

• 페이지가 빈 경우 free page 정보를 갱신해준다

• coalescence(merge)가 일어날 경우 페이지 정보 갱신이 필요하다.