Project2_Milestone1_3

Required changes for building on-disk b+tree

record 구조체의 구조 변경

• given b+ tree code는 record 구조체의 멤버 변수 value의 자료형을 int로 하고 있다.
• 하지만, Project 2의 disk-based b+ tree에서는 record(key + value)의 크기를 128(8+120)Bytes로 명시하고 있다.
• 따라서, record 구조체의 멤버 변수 value를 길이 120의 char 배열로 하거나, char 포인터로 두고 사용할 때 120Bytes를 가지도록 동적할당하여 사용해야 한다.

node 구조체를 page 구조체로 변경

• given b+ tree code에서 in-memory node로 사용되던 node 구조체 대신 in-memory page 구조체를 사용해야 한다.
• 4096Bytes의 크기를 가진다.
• 각 Header/Free/Leaf/Internal page로 사용될 구조체를 각각 구현하여, in-memory page 구조체가 pointing 하게 하거나, 동일한 pointer로 접근할 수 있게 하여 사용한다.
• Leaf page 구조체는 최대 31개의 record 구조체를 멤버로 가진다.

기본 command의 추가/변경

• Project 2에서는 open/insert/find/delete 4개 command를 구현하여 API services로 제공해야 한다.
• given b+ tree code는 in-memory b+ tree이므로, open <pathname>에 해당하는 함수가 존재하지 않는다. 따라서 다음과 같은 형태로 구현하여 추가해야 한다.

int open_table (char *pathname);

• insert <key><value> command, find <key> command, delete <key> command는

node * insert(node * root, int key, int value);
record * find(node * root, int key, bool verbose);
node * delete(node * root, int key);

위의 insert, find, delete 함수를 변경하여 다음과 같은 형태로 구현한다.

int db_insert(int64_t key, char * value);
int db_find(int64_t key, char * ret_val);
int db_delete(int64_t key);

• 각 함수는 변경된 record와 page 구조체를 활용하여 동작해야 한다.
• update operation(insert/delete)은 data file을 정확히 수정해야 하므로, 각 함수 내에서 추후 설명할 File manager API에 해당하는 함수들을 호출하여 data file의 수정을 온전히 마쳐야 한다.
• 즉, update operation은 memory 상에서 update 작업만 수행하고, 이후 추가적으로 실행되는 함수가 이를 data file에 최신화하는 것과 같은 경우는 절대 있어서는 안 된다.
• 각 함수는 call path를 따라서 다양한 관련 함수를 호출하므로, 해당하는 모든 함수들 또한 그에 맞게 변경해줘야 한다.

File manager API 추가

• layered architecture를 위해, File manger API를 추가해야 한다. 해당 함수들에서만 파일 입출력을 수행하도록 한다.
• 다음과 같이, on-disk page를 allocate/free/read/write하는 함수를 구현한다.

pagenum_t file_alloc_page();
void file_free_page(pagenum_t pagenum);
void file_read_page(pagenum_t pagenum, page_t* dest);
void file_write_page(pagenum_t pagenum, const page_t* src);

• file_alloc_page 함수는 free page list에 1개 on-disk page를 할당한다.
• file_free_page 함수는 지정한 on-disk page를 free page로 변경하고 free page list에 추가한다.
• file_read_page 함수는 지정한 on-disk page를 읽어서 in-memory page 구조체로 불러온다.
• file_write_page 함수는 in-memory page 구조체의 data를 지정한 on-disk page에 작성한다.

Delay Merge 구현

• B+ tree의 구조 변경(Split, Merge)은 disk-based B+ tree에서 성능 저하를 야기할 수 있으므로, Delay Merge를 구현하여 Merge 횟수를 감소시킨다. 또한 redistribute도 수행하지 않도록 하여 성능 저하를 방지한다.
• Merge는 delete 과정에서 발생하므로, delete 관련 함수들을 수정해야 한다.