Project2_Milestone2_2_Index Manager

Index Manager

Index

기존 bpt.c와의 차이점

INSERTION

db_make_record
db_make_page
db_make_leaf
db_get_left_index
db_insert_into_leaf
db_insert_into_leaf_after_splitting
db_insert_into_internal
db_insert_into_internal_after_splitting
db_insert_into_parent
db_insert_into_new_root
db_start_new_tree
db_insert

DELETION

db_get_index
db_get_neighbor_index
db_adjust_root
db_remove_entry_from_internal
db_remove_record_from_leaf
db_merge_pages
db_redistribute_pages
db_delete_entry
db_delete_record
db_delete

기존 bpt.c와의 차이점

1. node 포인터가 아닌 pagenum_t 변수를 사용

기존의 bpt.c는 in-memory b+tree 코드였기에 node 구조체와 그 포인터 변수를 이용해서 메모리에 저장된 트리와 각 노드간의 연결을 관리한다.
구현해야 하는 disk-based b+tree는 disk에 data가 저장되기에, 각 page의 연결을 포인터 변수가 아닌 page number로 관리한다.
따라서, node 구조체 대신 page_t 구조체를 사용하되 포인터 변수를 사용하지 않으며, page_t 구조체에서 다른 page를 가리키는 member 또한 포인터 변수가 아닌 pagenum_t 변수를 사용한다.
따라서, 각 함수들도 인자로 포인터 변수가 아닌 pagenum_t를 받고, 각각의 함수가 on-disk page를 read/write하며 작업을 수행한다.

2. One more page number를 고려하여 index 체크

기존의 bpt.c는 nonleaf node에서 ORDER-1 개의 key 배열과 ORDER 개의 pointer 배열을 이용해서 각 key와 child들을 관리한다.
구현해야 하는 disk-based b+tree는 internal page에서 ORDER-1 개의 key / page number 쌍을 가지고, 제일 좌측의 1개 page number는 One more page number로 따로 가진다.
따라서, internal page에서 key와 child들을 수정하는 작업을 할 때는, 기존 코드와는 달리 매 상황마다 One more page number를 따로 검사하거나 수정해주어야 한다.
leaf page는 ORDER-1 개의 key/record 쌍만 가지고 추가적인 key나 record가 존재하지 않으므로 이런 처리는 필요하지 않다.

delayed merge 구현

기존의 bpt.c는 ORDER의 절반이 조금 안 되는 특정 최소 개수 이하로 키 개수가 내려가면 이웃 노드와 merge / redistribution을 수행한다. merge 시 1개 노드의 최대용량을 넘을 경우 redistribution, 그렇지 않을 경우 merge를 수행한다. 이는 leaf / nonleaf node를 가리지 않는다.
B+ tree의 구조 변경(Split, Merge)은 disk-based B+ tree에서 성능 저하를 야기할 수 있으므로, Delay Merge를 구현하여 Merge 횟수를 감소시켜야 한다.
따라서 key 개수가 0개가 되어야만 merge / redistribution을 수행한다.
leaf page에서 해당 상황 발생 시, key/record 쌍이 모두 지워져서 해당 page가 가지고 있는 data가 없으므로, merge / redistribution 없이 해당 page의 부모 page에서 해당 page를 삭제하는 작업을 바로 실행한다. 즉, merge / redistribution은 internal page에만 적용된다.
즉, key 1개와 child 2개를 가진 internal page에서 child 1개가 삭제되어, key 0개와 child 1개를 가지게 된 상태에서만 merge / redistribution을 수행한다.
merge : 남은 1개의 child를 이웃 page에 넘겨주고 해당 page를 삭제한다.
- 이웃 page가 현재 최대용량일 경우 child를 넘겨줄 수 없기에 merge가 불가하다.
redistribution : 이웃 page의 key와 child를 일부 가져와서 현재 page의 key 개수가 1개 이상이 되도록 한다. (1개 key/child 쌍만 가져올 수도 있고 insert에서 split할 때와 유사하게 약 절반을 가져올 수 있다. 현재 약 절반을 가져오는 것으로 구현.)
- 이웃 page가 key 1개와 child 2개를 가지고 있을 시 key와 child를 가져올 수 없기에 redistribution이 불가능하다.
따라서 둘 다 구현해야 하며, 두 가지 중 한 가지가 불가능한 상황이 아닐 경우, 한 쪽을 우선적으로 사용할 수 있다. (현재 redistribution을 우선적으로 사용하도록 구현. merge 최소화.)

UTILITIES

1. cut

int cut(int length)

노드를 분할할 적절한 위치를 찾는다.

인자
- length (int) : 분할할 노드의 최대 key 개수. (order-1).
반환 : (int)
- 인자로 받은 length를 가지는 노드를 분할할 적절한 위치.

2. db_find_left_leaf

pagenum_t db_find_left_leaf(pagenum_t pagenum)

현재 tree에서 입력받은 pagenum에 해당하는 page의 왼쪽 leaf page를 탐색한다.

인자
- pagenum (pagenum_t) : 왼쪽 left page를 찾고자 하는 page의 page number.
반환 : (pagenum_t)
- 입력받은 pagenum에 해당하는 page의 왼쪽 page의 page number.

leaf page 중 가장 왼쪽의 page를 탐색한다.
가장 왼쪽 leaf page부터 시작해서 right sibling page를 탐색해나가며 입력받은 page number가 있는지 확인한다.
- 가장 왼쪽 leaf page의 page number가 입력받은 page number일 경우,왼쪽 leaf page가 존재하지 않으므로 -1을 반환한다.
- 끝까지 탐색해도 입력받은 page number를 찾을 수 없으면, 입력받은 page number가 정상적인 leaf page의 page number가 아니므로 -2를 반환한다.
- 있을 경우, 현재 확인 중인 page, 즉 right sibling page number로 입력받은 page number를 가지는 page의 page number를 반환한다.

OPEN

1. open_table

int open_table(char * pathname)

1개 테이블, 즉 1개 파일을 open한다.

인자
- pathname (char*) : 열고자 하는 file의 경로, 이름.
반환 : (int)
- 열기 성공 시 해당 table의 unique table id.
- 열기 실패 시 negative value.

Disk Space Manager의 file_open 함수를 이용해서 입력받은 경로의 파일을 open한다. 반환값을 int unique_table_id 변수에 저장한다.
- 성공 시, 파일 앞에서 전역변수로 선언하고 0으로 초기화한 변수 int opened에 1을 저장한다.
unique_table_id 변수를 반환한다.
- 성공 시, 0 이상의 unique table id가 반환된다.
- 실패 시, negative value가 반환된다.

FIND

1. db_find_leaf

pagenum_t db_find_leaf(int64_t key)

현재 tree에서 입력받은 key를 포함하는 범위의 leaf page를 탐색한다.

인자
- key (int64_t) : 탐색할 key.
반환 : (pagenum_t)
- 현재 tree에서 입력받은 key를 포함하는 범위의 leaf page의 page number.

root page가 존재하지 않을 경우 0을 반환한다.
root page부터 시작해서 입력받은 key를 포함하는 범위의 page를 탐색해나가며, 최종적으로 해당 key를 포함하는 범위의 leaf page를 찾아 해당 page의 page number를 반환한다.

2. db_find

int db_find(int64_t key, char * ret_val)

현재 tree에서 입력받은 key를 가지는 record를 탐색한다.

인자
- key (int64_t) : 탐색할 key.
- ret_val (char*) : 탐색한 record가 가지는 value를 담을 char 포인터.
반환 : (int)
- 성공 시 0.
- 실패 시 no-zero value.

table의 open 여부를 확인하고, open되어 있지 않을 경우 안내 문구 출력 후 -1을 반환한다.
db_find_leaf 함수를 call하여 현재 tree에서 입력받은 key를 포함하는 범위의 leaf page를 탐색한다.
- 존재하지 않을 경우, -2를 반환한다.
해당 leaf page에서 입력받은 key를 가지는 record를 탐색한다.
- 존재하지 않을 경우, -3을 반환한다.
해당 record의 value를 ret_val에 복사하고 0을 반환한다.

INSERTION

1. db_make_record

record db_make_record(int64_t key, char * value)

입력받은 key와 value를 가지는 record를 생성한다.

인자
- key (int64_t) : 생성할 record가 가질 key.
- value (char*) : 생성할 record가 가질 value.
반환 : (record)
- 인자로 받은 key와 value를 가지는 새로운 record.

record 구조체를 선언하고 memset 함수로 초기화한다.
입력받은 key와 value를 선언한 구조체에 복사한다.
해당 record 구조체를 반환한다.

2. db_make_page

page_t db_make_page()

leaf page / internal page로 사용될 수 있는 일반적인 page를 생성한다.

반환 : (page_t)
- 생성한 page_t 구조체.

page_t 구조체를 선언하고 memset 함수 등을 이용해 초기화한다.
해당 page_t 구조체를 반환한다.

3. db_make_leaf

page_t db_make_leaf()

leaf page를 생성한다.

반환 : (page_t)
- 생성한 page_t 구조체.

page_t 구조체를 선언하고 db_make_page 함수를 call하여 생성한 page를 저장한다.
구조체의 is_leaf 값을 1로 저장하고 해당 page_t 구조체를 반환한다.

4. db_get_left_index

int db_get_left_index(pagenum_t parent_pagenum, pagenum_t left_pagenum)

부모 page에서 left page의 index를 확인한다.

인자
- parent_pagenum (pagenum_t) : left page의 부모 page의 page number.
- left_pagenum (pagenum_t) : index를 확인할 page의 page number.
반환 : (int)
- 부모 internal page가 가지고 있는 page number들 중 left page의 index.

부모 internal page가 가지고 있는 page number들 중 left page의 page number가 몇 번째 index에 삽입되어 있는지 확인하고, 그 값을 반환한다.
- 제일 좌측의 page number, 즉 one more page number의 경우 -1을 그 index로 한다.

5. db_insert_into_leaf

int db_insert_into_leaf(pagenum_t pagenum, record new_record)

leaf page에 record를 삽입한다.

인자
- pagenum (pagenum_t) : 해당 record를 삽입할 leaf page의 page number.
- new_record (record) : 삽입할 record 구조체.
반환 : (int)
- 성공 시 0.
- 실패 시 non-zero value. (error checking 추가 예정.)

leaf page에 이미 존재하는 record들 사이에서 입력받은 record가 삽입될 적절할 위치를 찾는다.
해당 위치를 비우기 위해 그 위치부터 그 이후의 record들을 한 칸씩 미루는 작업을 수행한다.
비운 위치에 입력받은 record를 삽입한 후 성공 여부(성공 시 0)를 반환한다.

6. db_insert_into_leaf_after_splitting

int db_insert_into_leaf_after_splitting(pagenum_t pagenum, record new_record)

leaf page를 분할한 후 record를 삽입한다.

인자
- pagenum (pagenum_t) : 해당 record를 삽입할 leaf page(분할될 page)의 page number.
- new_record (record) : 삽입할 record 구조체.
반환 : (int)
- 성공 시 0.
- 실패 시 non-zero value. (error checking 추가 예정.)

page 구조체 new_leaf를 선언하고 db_make_leaf 함수로 초기화한다.
임시 record 배열을 선언한다. 그 크기는 leaf page가 갖는 크기보다 1 크게 한다.
leaf page에 이미 존재하는 record들 사이에서, 입력받은 record가 삽입될 적절한 위치를 찾는다.
leaf page의 record들을 임시 변수에 복사하되, 위에서 찾은 위치를 비우고 해당 위치부터 그 이후 record들은 한 칸씩 뒤로 복사한다.
인자로 받은 record를 임시 변수의 해당 위치에 삽입한다.
cut 함수를 call하여 leaf node를 분할할 적절한 위치를 확인한다.
임시 변수로부터 분할될 왼쪽 절반 record들을 leaf page로 복사한다. 이 때 leaf page의 number of keys도 갱신한다.
임시 변수로부터 분할될 오른쪽 절반 record들을 new_leaf(새로 생성한 leaf page 구조체)로 복사한다. 이의 number of keys도 갱신한다.
disk에 새로운 page를 할당하고, new_leaf를 write한다. 기존 leaf page도 write하여 갱신한다.
db_insert_into_parent 함수를 call하여 new_leaf(새로 생성한 leaf page)를 부모 page에 삽입하고 그 결과를 반환한다.

7. db_insert_into_internal

int db_insert_into_internal(pagenum_t parent_pagenum, int left_index, int64_t key, pagenum_t right_pagenum)

분할로 생성된 page를 부모 page에 삽입한다.

인자
- parent_pagenum (pagenum_t) : 삽입하려는 page의 부모 page의 page number.
- left_index (int) : 삽입하려는 page의 왼쪽에 위치할 page가 부모 page에서 가지는 index.
- key (int64_t) : 삽입하려는 page와 그 왼쪽에 위치할 page 사이의 key.
- right_pagenum (pagenum_t) : 삽입하려는 page의 page number.
반환 : (int)
- 성공 시 0.
- 실패 시 non-zero value. (error checking 추가 예정.)

right page와 key가 삽입될 위치를 비우기 위해 해당 위치부터 그 이후 page와 key들을 한 칸씩 뒤로 미루는 작업을 수행한다.
해당 위치에 right page와 key를 삽입한 후, 성공 여부(성공 시 0)를 반환한다.

8. db_insert_into_internal_after_splitting

int db_insert_into_internal_after_splitting(pagenum_t parent_pagenum, int left_index, int64_t key, pagenum_t right_pagenum)

부모 page를 분할하고 right page를 적절한 위치에 삽입한다.

인자
- parent_pagenum (pagenum_t) : 삽입하려는 page의 부모 page(분할될 node)의 page number.
- left_index (int) : 삽입하려는 page의 왼쪽에 위치할 page가 부모 page에서 가지는 index.
- key (int64_t) : 삽입하려는 page와 그 왼쪽에 위치할 page 사이의 key.
- right_pagenum (pagenum_t) : 삽입하려는 page의 page number.
반환 : (int)
- 성공 시 0.
- 실패 시 non-zero value. (error checking 추가 예정.)

page 구조체 new_internal을 선언하고 db_make_page 함수로 초기화한다.
임시 entry 배열과 one more page number 변수를 선언한다. 그 크기는 internal page가 갖는 크기보다 1 크게 한다.
parent page의 자녀 page와 key들을 임시 변수에 복사하되, 삽입할 node와 key를 위한 공간을 비우고 해당 위치부터 그 이후 자녀 node와 key들은 한 칸씩 뒤로 복사한다.
인자로 받은 right_pagenum과 key를 임시 변수의 해당 위치에 삽입한다.
cut 함수를 call하여 부모 node를 분할할 적절할 위치를 확인한다.
임시 변수로부터 분할될 왼쪽 절반 pagenum과 key들을 parent page로 복사한다.
임시 변수로부터 분할될 오른쪽 절반 pagenum과 key들을 new_internal(새로 생성한 internal page 구조체)으로 복사한다.
disk에 새로운 page를 할당하고, new_internal을 write한다. 기존 parent page도 write하여 갱신한다. 부모 page가 바뀐 각각의 child page들도 이를 최신화한다.
db_insert_into_parent 함수를 call하여 new_internal(새로 생성한 internal page)를 부모 page에 삽입하고 그 결과를 반환한다.

9. db_insert_into_parent

int db_insert_into_parent(pagenum_t left_pagenum, int64_t key, pagenum_t right_pagenum)

분할로 추가 생성된 page를 부모 page에 삽입한다.

인자
- left_pagenum (pagenum_t) : 분할된 첫 번째 page의 page number. 이미 부모 page가 갖고 있음.
- key (int64_t) : 2개 page 사이의 key.
- right_pagenum (pagenum_t) : 분할된 두 번째 page(삽입할 page)의 page number.
반환 : (int)
- 성공 시 0.
- 실패 시 non-zero value. (error checking 추가 예정.)

부모 page가 존재하지 않을 경우, 즉 root page가 분할된 상태일 경우, db_insert_into_new_root 함수를 call하여 새로운 root page를 생성하고 2개 page를 그에 삽입한다. 그 결과를 반환한다.
db_get_left_index 함수를 call하여 부모 page에서 left page의 index를 확인한다.
부모 page에 right page가 삽입될 여유 공간이 있을 경우, db_insert_into_internal 함수를 call하여 삽입을 수행하고 그 결과를 반환한다.
부모 page에 여유 공간이 없을 경우, 즉 분할이 필요할 경우, db_insert_into_internal_after_splitting 함수를 call하여 부모 node의 분할을 동반한 삽입을 수행하고 그 결과를 반환한다.

10. db_insert_into_new_root

int db_insert_into_new_root(pagenum_t left_pagenum, int64_t key, pagenum_t right_pagenum)

새로운 root page를 생성하고 분할된 2개 page(subtree)를 삽입한다.

인자
- left_pagenum (pagenum_t) : 분할된 첫 번째 page의 page number.
- key (int64_t) : 2개 page 사이의 key.
- right_pagenum (pagenum_t) : 분할된 두 번째 page의 page number.
반환 : (int)
- 성공 시 0.
- 실패 시 non-zero value. (error checking 추가 예정.)

db_make_page 함수를 call하여 새로운 page 구조체를 생성한다.
page 구조체를 초기화하고 인자로 받은 2개 page(subtree)를 삽입한 후, disk에 page를 할당하여 이를 write한다.
해당 페이지가 root page가 되도록 header page를 최신화하고, 이의 자녀 page가 된 2개 page도 해당 page를 parent page로 가리키도록 최신화한다.
성공 여부(성공 시 0)를 반환한다.

11. db_start_new_tree

int db_start_new_tree(record new_record)

처음 입력된 record를 가지는 새로운 tree를 생성한다.

인자
- new_record (record) : 삽입할 record.
반환 : (int)
- 성공 시 0.
- 실패 시 non-zero value. (error checking 추가 예정.)

db_make_leaf 함수를 call하여 새로 만든 leaf page, root를 생성한다.
해당 구조체를 초기화하며 인자로 받은 record를 저장한 후, disk에 page를 할당하고 이를 write한다.
해당 페이지가 root page가 되도록 header page를 최신화한다.
성공 여부(성공 시 0)를 반환한다.

12. db_insert

int db_insert(int64_t key, char * value)

현재 tree에 입력받은 record를 삽입한다.

인자
- key (int64_t) : 삽입할 record의 key.
- value (char*) : 삽입할 record의 value.
반환 : (int)
- 성공 시 0.
- 실패 시 non-zero value. (error checking 추가 예정.)

table의 open 여부를 확인하고, open되어 있지 않을 경우 안내 문구 출력 후 -1을 반환한다.
db_find 함수를 call하여 입력받은 key와 동일한 key를 가진 record가 tree에 이미 존재하는지 여부를 확인한다.
- 존재할 경우, 삽입 작업을 중단하고 -2를 반환한다. (즉, 중복 key를 허용하지 않는다.)
db_make_record 함수를 call하여 입력받은 key/value를 가지는 새 record를 생성한다.
삽입할 tree가 비었는지 확인한다.
- 비어있을 경우, db_start_new_tree 함수를 call하여 새로 생성한 record를 가지고 새로운 tree를 생성한 후 그 결과를 반환한다.
db_find_leaf 함수를 call하여 입력받은 key를 포함하는 범위의 leaf page를 찾는다.
해당 leaf page에 record가 들어갈 여유 공간이 있는지 확인한다.
- 있을 경우, db_insert_into_leaf 함수를 call하여 해당 leaf page에 record를 삽입한 후 그 결과를 반환한다.
- 없을 경우, 즉 분할이 필요할 경우, db_insert_into_leaf_after_splitting 함수를 call하여, 해당 leaf page의 분할을 동반한 삽입을 수행하고 그 결과를 반환한다.

DELETION

1. db_get_index

int db_get_index(pagenum_t pagenum)

입력받은 page의 index를 확인한다.

인자
- pagenum (pagenum_t) : index를 확인할 page의 page number.
반환 : (int)
- 입력받은 page의 index.

입력받은 page의 부모 page에서 입력받은 page의 index를 확인하고, 해당 index를 반환한다.
- 해당 page가 가장 왼쪽 page(one more page)였을 경우 -1이 반환된다.

2. db_get_neighbor_index

int db_get_neighbor_index(pagenum_t pagenum)

입력받은 page의 왼쪽 형제 page의 index를 확인한다.

인자
- pagenum (pagenum_t) : 왼쪽 형제의 index를 확인할 page의 page number.
반환 : (int)
- 입력받은 page의 왼쪽 형제 page의 index.

입력받은 page의 부모 page에서 입력받은 page의 index를 확인하고, (해당 index) - 1, 즉 해당 page의 왼쪽 형제 page의 index를 반환한다.
- 해당 page가 가장 왼쪽 page(one more page)였을 경우 -2이 반환된다.
- 왼쪽 형제 page가 가장 왼쪽 page(one more page)였을 경우 -1이 반환된다.

3. db_adjust_root

int db_adjust_root()

삭제가 발생한 root page를 조정한다.

반환 : (int)
- 성공 시 0.
- 실패 시 non-zero value. (error checking 추가 예정.)

root page가 비었는지 확인한다. 비어있지 않은 경우, 성공(0)을 반환한다.
root page가 internal 또는 leaf page인지 확인한다.
- internal page일 경우, 단 하나 있는 첫 번째 자녀 page를 새로운 root page로 둔다. 이에 따라 header page와 해당 자녀 page를 최신화하여 write한다. 해당 page는 free한다.
- leaf page일 경우, header page에서 root page number를 0으로, 즉 존재하지 않는 것으로 한다. 해당 page는 free한다.
성공 여부(성공 시 0)를 반환한다.

4. db_remove_entry_from_internal

int db_remove_entry_from_internal(pagenum_t pagenum)

internal page에서 자녀 page를 삭제한다.

인자
- pagenum (pagenum_t) : 삭제할 page의 page number.
반환 : (int)
- 성공 시 0.
- 실패 시 non-zero value.

현재 page가 leaf page일 경우, 좌우의 page를 link해준다.
해당 page의 부모 page에서 해당 page를 삭제한다.
해당 page가 삭제되어 1 감소한 부모 page의 number of keys를 확인한다.
- 0일 경우, db_delete_entry 함수를 call하여 해당 부모 페이지도 삭제하도록 하고 그 결과를 반환한다.
- 0이 아닐 경우, 0(성공)을 반환한다.

5. db_remove_record_from_leaf

int db_remove_record_from_leaf(pagenum_t leaf_pagenum, int64_t key)

leaf page에서 record를 삭제한다.

인자
- leaf_pagenum (pagenum_t) : 삭제할 record가 들어있는 leaf page의 page number.
- key (int64_t) : 삭제할 record의 key.
반환 : (int)
- 성공 시 0.
- 실패 시 non-zero value.

해당 leaf page에서 해당 record를 삭제한다.
위의 db_remove_entry_from_internal 함수와는 달리, 이 함수를 호출하는 db_delete_record에서 key가 0이 되었는지를 확인하기 때문에 현재 여기서는 확인하지 않음, 추후 통일할 예정.

6. db_merge_pages

int db_merge_pages(pagenum_t current_pagenum, pagenum_t neighbor_pagenum,
        int neighbor_index, int k_prime_index, int64_t k_prime)

2개 page를 merge, 실질적으로 1개 page를 삭제한다.

현재 page가 0개의 key, 형제 page가 1개 key를 가지고 있을 때만 실행된다.
인자
- current_pagenum (pagenum_t) : merge하고자 하는 1번째 page(실질적으로 삭제될 page)의 page number.
- neighbor_pagenum (pagenum_t) : merge하고자 하는 2번째 page. 1번째 page의 형제 page.
- neighbor_index (int) : 형제 page의 index.
- k_prime_index (int) : 2개 page의 부모 page에서 k_prime의 index.
- k_prime (int64_t) : 2개 page 사이의 key.
반환 : (int)
- 성공 시 0.
- 실패 시 non-zero value.

현재 page가 가지고 있는 1개의 유일한 자녀 page를 형제 page로 넘겨준다. neighbor_index를 이용하여 둘 중 어느 page과 왼쪽이고 오른쪽인지를 판단하여 적절하게 넘겨준다.
옮겨준 자녀 page의 부모 page를 형제 page로 최신화한다. 형제 page도 변경사항을 write한다.
db_remove_entry_from_internal 함수를 call하여 현재 page를 삭제하고 그 결과를 반환한다.

7. db_redistribute_pages

int db_redistribute_pages(pagenum_t current_pagenum, pagenum_t neighbor_pagenum,
        int neighbor_index, int k_prime_index, int64_t k_prime)

2개 page가 가지고 있는 자녀 page를 재분배한다.

현재 page가 0개의 key, 형제 page가 1개 초과의 key를 가지고 있을 때만 실행된다.
인자
- current_pagenum (pagenum_t) : 재분배하고자 하는 1번째 page의 page number.
- neighbor_pagenum (pagenum_t) : 재분배하고자 하는 2번째 page. 1번째 page의 형제 page.
- neighbor_index (int) : 형제 page의 index.
- k_prime_index (int) : 2개 page의 부모 page에서 k_prime의 index.
- k_prime (int64_t) : 2개 page 사이의 key.
반환 : (int)
- 성공 시 0.
- 실패 시 non-zero value.

insert 시 발생하는 split과 유사하게, 형제 page가 가지고 있는 key와 자녀 page들의 약 절반을 현재 page로 옮긴다. neighbor_index를 이용하여 둘 중 어느 page과 왼쪽이고 오른쪽인지를 판단하여 적절하게 옮긴다.
옮겨준 자녀 page의 부모 page를 현재 page로 최신화한다. 현재 page와 형제 page도 변경사항을 write한다.
0(성공)을 반환한다.

8. db_delete_entry

int db_delete_entry(pagenum_t pagenum)

현재 tree에서 입력받은 page를 삭제한다.

인자
- pagenum (pagenum_t) : 삭제할 page의 page number.
반환 : (int)
- 성공 시 0.
- 실패 시 non-zero value.

해당 page가 leaf page일 경우 db_remove_entry_from_internal 함수를 call하여 해당 page를 삭제하고 그 결과를 반환한다.
해당 page가 현재 tree의 root page일 경우, db_adjust_root 함수를 call하여 root page를 조정하고 그 결과를 반환한다.
merge하기에 적절한 형제 node를 찾는다. 이 과정에서 db_get_neighbor_index 함수를 call하여 사용한다.
- merge가 필수적일 경우, 즉 현재 page는 0개의 key, 형제 page는 1개의 key를 가진 internal page일 경우, db_merge_pages 함수를 call하여 merge를 실행하고 그 결과를 반환한다.
- merge가 필수적이지 않을 경우, db_redistribute_pages 함수를 call하여 재분배를 실행하고 그 결과를 반환한다.

9. db_delete_record

int db_delete_record(pagenum_t leaf_pagenum, int64_t key)

현재 tree에서 입력받은 key를 가지는 record를 삭제한다.

인자
- leaf_pagenum (pagenum_t) : 삭제할 record를 가진 leaf page의 page number.
- key (int64_t) : 삭제할 record의 key.
반환 : (int)
- 성공 시 0.
- 실패 시 non-zero value.

db_remove_record_from_leaf 함수를 call하여 입력받은 leaf page에서 입력받은 record를 삭제한다.
입력받은 leaf page가 현재 tree의 root page인지 확인한다.
- root page일 경우 db_adjust_root 함수를 call하여 root page를 조정하고 그 결과를 반환한다.
leaf page의 key 개수를 확인한다.
- 0이 아닐 경우 성공(0)을 반환한다.
- 0일 경우 db_delete_entry 함수를 call하여 해당 page의 삭제를 수행하고 그 결과를 반환한다.

10. db_delete

int db_delete(int64_t key)