Disk Based B Plus Tree

Disk-based B+ tree

1. Possible call path of the insert/delete operation

Insert Operation

주어진 key를 삽입하기
"node * insert( node * root, int key, int value )"
 → 해당 key를 어디에 삽입할 지 찾기
 "record * find( node * root, int key, bool verbose )"
     → 1. 추가할 key가 이미 존재한다면, 이미 존재하는 record를 return
     → 2. 추가할 key가 없다면, 새로운 key를 추가하기 위해 레코드를 만든다.
     "record* make_record(int value)"
         → 2.1 새로운 레코드를 추가할 트리가 없다면, 새로운 트리를 만들고 레코드를 추가한다.
         "node * start_new_tree(int key, record * pointer)"
         → 2.2 새로운 레코드를 추가할 트리가 있다면, 들어갈 자리를 찾는다
         "node * find_leaf( node * root, int key, bool verbose )"
             → 2.2.1 들어갈 자리에 공간이 있으면, 적절한 위치에 삽입한다.
             "node * insert_into_leaf( node * leaf, int key, record * pointer )"
             → 2.2.2 들어갈 자리에 공간이 없으면, split후 추가한다.
             "node * insert_into_leaf_after_splitting(node * root, node * leaf, int key, record * pointer)"

Delete Operation

주어진 key를 제거하기
"node * delete( node * root, int key )"
 → 1. 제거할 key가 어디에 있는 지 찾기
 "record * find( node * root, int key, bool verbose )"
 → 2. 제거할 record가 있는 leaf 노드를 찾기
 "node * find_leaf( node * root, int key, bool verbose )"
     → 2.1. 제거할 key가 없거나 그에 해당하는 record가 없다면, 기존의 root를 return
     → 2.2 제거할 key에 해당하는 record가 있다면, 해당 레코드를 삭제한 후 변경된 root를 return
     "node * delete_entry( node * root, node * n, int key, void * pointer ) & free(key_record)"

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

Split

Split을 하는 시점 : 레코드를 추가하려는 위치에 해당하는 leaf 노드가 full일 때

Split을 하는 지점 : leaf node, internal node(including root node)

1. Root node에서 split을 하는 경우(자식 노드에서 recursive하게 split이 전달된 경우, root 노드가 꽉 찬 경우)
   • 1-1. Root node를 절반씩 고르게 나눈다.
   • 1-2. 나머지 절반에 대한 keys와 pointers을 새로운 leaf 노드에 담는다.
   • 1-2. 기존의 node를 leaf 노드가 되도록 flag를 설정한다.
   • 1-3. 키를 적절한 위치에 추가또는 update한다.
   • 1-4. 새로 만들어진 노드의 가장 왼쪽 key를 Middle key로 삼아 split된 노드의 부모 노드(새로운 root 노드를 만들어야 함)로 push up한다.
2. Root node가 아닌 internal node에서 split을 하는 경우(자식 노드에서 recursive하게 split이 전달된 경우)
   • 2-1. Split의 대상이 되는 Internal node를 절반씩 고르게 나눈다.
   • 2-2. 나머지 절반에 대한 keys와 pointers을 새로운 internal 노드에 담는다.
   • 2-3. 자식 노드에서 push up( 또는 copy)된 key를 적절한 위치에 추가또는 update한다.
   • 2-4. 새로 만들어진 노드의 가장 왼쪽 key를 Middle key로 삼아 split된 노드의 부모 노드로 push up한다.
3. Leaf node에서 split을 하는 경우
   • 3-1. Split의 대상이 되는 leaf node를 절반씩 고르게 나눈다.
   • 3-2. 나머지 절반에 대한 keys와 pointers을 새로운 leaf 노드에 담는다.
   • 3-3. key를 적절한 위치에 추가한다.
   • 3-4. 새로 만들어진 노드의 가장 왼쪽 key를 Middle key로 삼아 split된 노드의 부모 노드로 copy한다.

Merge

Merge을 하는 시점 : 레코드를 제거하려는 위치에 해당하는 leaf 노드가 인접한 친척 노드(sibling node)로부터 key redistribution을 통해 key invariants 를 만족시킬 수 없을 때

Merge을 하는 지점 : leaf node, internal node(including root node)

1. Internal node에서 Merge가 될 경우
   • 1-1. 삭제할 레코드를 삭제하고, 인접한 sibling node(right node)의 모든 레코드를 가져온다.
   • 1-2. 부모 노드에 있는 splitting key를 제거하고 합병된 노드를 제거된 splitting key 다음에 있는 key의 왼쪽 포인터가 가리키도록 설정한다.
   • 1-3. 인접한 sibling node(right node)를 할당 해제한다. (Disk-based의 경우 free page에 추가.)
2. Leaf node에서 Merge가 될 경우
   • 2-1. 삭제할 레코드를 삭제하고, 인접한 sibling node(right node)의 모든 레코드를 가져온다.
   • 2-2. 인접한 sibling node(right node)를 할당 해제한다. (Disk-based의 경우 free page에 추가.)

3. Pagination Strategy (Naive designs or required changes for building on-disk b+ tree)

Disk I/O

• how to? using some OS system calls such as open, close, write, read, fsync, and lseek
• Pagination
  1. Slotted Pages : after the completion of pagenated B+ tree, I'll make it.
  2. Record Format : Fixed-size record(key+value)
  3. Key size : 과제에서 주어진 B+ Tree 코드에서 key의 크기는 4-byte int로 되어있지만, 과제의 요구사항은 8-byte unsigned int이고 offset이므로 이 부분을 disk-based b+ tree에 맞도록수정하여야 한다.
• Solutions to treat heavy disk I/O
  • Delayed Merge : key invariant를 만족하지 않더라도 key가 다 비워질 때 까지 Merge를 하지 않는 것
  • Support Bulk Loading : Prefectching, CPU Cache Hit Ratio를 높이기 위한 것
  • Double Buffering(Disk Latency Hiding) : I/O Speed Gap among CPU, Cache, RAM, Disk를 병렬처리를 통해 숨기는 것
• File Manager APIs
  • Redefinitions of the page layout(page_t) and the page number(pagenum_t)
  • pagenum_t file_alloc_page() : Allocate an on-disk page from the free page list
  • void file_free_page(pagenum_t pagenum) : Free an on-disk page to the free page list
  • void file_read_page(pagenum_t pagenum, page_t* dest) : Read an on-disk page into the in-memory page structure(dest)
  • void file_write_page(pagenum_t pagenum, const page_t* src) : Write an in-memory page(src) to the on-disk page
• Implement 4 commands using File Manager APIs
  1. open <pathname>
     • Open existing data file using ‘pathname’ or create one if not existed.
     • All other 3 commands below should be handled after open data file.
  2. insert <key> <value>
     • Insert input ‘key/value’ (record) to data file at the right place.
     • Same key should not be inserted (no duplicate).
  3. find <key>
     • Find the record containing input ‘key’ and return matching ‘value’ or ‘null’ if not found.
  4. delete <key>
     • Find the matching record and delete it if found.