Skip to content
NamJiii edited this page Oct 22, 2020 · 1 revision

Disk Based B+ Tree

데이터베이스시스템및응용 Prof. 정형수

2017029561 컴퓨터소프트웨어학부 남지훈

0. Structures

DB file 을 관리 하기 위해 파일 안에 있는 데이터를 읽고, 수정한 다음 쓰는 과정을 거쳐야 한다. 이를 위해서 db file 에 존재하는 page를 메모리상에 읽어올 수 있는 구조체가 필요하다.

Record Structure


typedef struct record {
	int64_t key; 
	char value[120];
} record;

leaf page 에 들어갈 record에 해당하는 구조체 이다.

문자열 데이터를 받을 수 있는 120byte char 배열과, 문자열 데이터를 구분하기 위한 key값이 포함된다.

Internal Page Key and Offset Structure


typedef struct key_and_offset {
	int64_t key;
	off_t child_off;
} KeyOff;

leaf page로부터 복제한 key 값과 그 leaf page의 offset 이 포함된다.

Header Page Structure


typedef struct header_page {
	off_t free_off;//[0-7] free page offset
	off_t root_off;//[8-15] root page offset
	int64_t num_pages;// [16-23] number of pages
	char reserved[4072];//reserved
} header_page;

header page만을 위한 structure 이다. free page list 와 root page offset, 그리고 DB 가 가지고 있는 page 의 총개수에 대한 정보를 포함하고 있다.

The Other Page Structure


typedef struct page_t { // 4096Byte
	off_t parent;
	int is_leaf;
	int num_keys;
	char reserved[104];
	off_t ex_off;
	union {
		KeyOff branches[248]; // (internal) MAX 248 (key8+offset8) 
		record records[31]; // leaf MAX 31 (key8+offset120) 
	};
}page_t;

이 structure는 internal page 와 leaf page 에서의 일반적인 사용을 위해 union을 이용하였다. union 내부에는 page header을 제외한 실질적인 데이터 3968byte 가 저장된다.

page header 에는 parent page offset, leaf/internal 구분 변수, key의 갯수, 그리고 추가적으로 offset을 담기위한 extra offset을 저장한다.

1. Open DB

disk-based 이기 때문에 데이터를 쓰고 읽을 DB파일을 열어 관리하여야 한다. 이를 위해 DB를 여는 함수를 구현한다.

Make new DB file


   db_fd = open(pathname, O_RDWR | O_CREAT | O_EXCL | O_SYNC, 0777);
   if (db_fd > 0) {
      headerP->num_pages = 1;
      temp = pwrite(db_fd, headerP, PAGESIZE, 0);}

open 할 수 있는 DB file 이 없을때에는 새로 생성하여 만들어야 한다. 위의 코드가 그 역할을 한다.

Open an existing DB file.

 
   db_fd = open(pathname, O_RDWR | O_SYNC);
   if (db_fd > 0) {
      temp = pread(db_fd, headerP, PAGESIZE, 0); }

이미 DB file 이 존재한다면, 그 파일의 0번째 offset 에 있는 header page의 정보를 메모리에 할당되어있는 headerP 변수에 read 한다.

2. Find Operation

DB 에 저장된 데이터를 읽고, 쓰고 또는 지우기 위해서 해당 데이터의 key 값을 찾는것이 필요하다. 이러한 과정을 Find() 함수에서 구현한다.

master find function


char * find(int64_t key) {
    int i = 0;
    pagenum_t pagenum;

    pagenum = find_leaf( key );
    page_t * c =(page_t *) calloc(1,PAGESIZE);
    file_read_page(pagenum,c);

    if (pagenum == 0) return NULL;
    for (i = 0; i < c->num_keys; i++)
        if (c->records[i].key == key) break;
    
    if (i == c->num_keys) {
    	free(c);
    	return NULL;
    }
    else{
    	char *a;
    	a = c->records[i].value;
    	free(c);
    	return (char *)a;
    }
}

find_leaf 함수를 통해 해당 key가 포함된 범위의 key값을 가지고 있는 page를 찾는다. 이후, 그페이지에 내가 찾고자 하는 key값과 동일한 key값이 존재하는지 검사한후, 존재하면 value를, 존재하지 않으면 NULL 을 return 한다.

Find Page Operation


pagenum_t find_leaf(int64_t key ) {
    int i = 0;
    off_t temp;
	page_t * c = (page_t *)calloc(1,PAGESIZE);
	temp = off_to_num(headerP->root_off);
    file_read_page(temp, c);
    if (temp == 0){
    	free(c);
    	return 0;
    } 

    while (!c->is_leaf) {
        i = -1;
        while (i <= c->num_keys) {
            if (key >= c->branches[i+1].key && inum_keys-1) {
				i++;
            }
            else break;
        }
        if (i == c->num_keys){
        	free(c);
        	return 0;}
        else if(i==-1)
        	temp = off_to_num(c->ex_off);
        else
        temp = off_to_num(c->branches[i].child_off);
        file_read_page(temp,c);
    }
    free(c);

    return temp;
}

입력한 key값의 범위에 해당하는 page를 찾는 함수이다. 찾고자 하는 key값이 없더라도, 입력받은 key값보다 작은 key와 큰 key를 포함하고 있다면, 입력받은 key값이 들어갈 수 있는 자리라고 판단하여 그 페이지의 pagenum을 return 해준다.

3. Inserte and Delete Operation

Insert operation

Master Insertion Code


pagenum_t insert(int64_t key, char value[120] ) {

    page_t * leafP = calloc(1,PAGESIZE);
    pagenum_t leaf;

	int root = off_to_num(headerP->root_off);
	file_read_page(root,rootP);

    if (find(key) != NULL){
    	free(leafP);
    	return 0;
    }


    if (rootP == NULL) 
        return start_new_tree(key, value);

    leaf = find_leaf(key);
	file_read_page(leaf,leafP);

    if (leafP->num_keys < order - 1) {
        leaf = insert_into_leaf(leaf, key, value);
        free(leafP);
        return leaf;
    }

     free(leafP);

    return insert_into_leaf_after_splitting(leaf, key, value);
}

Overall Call Path of Insertion

1) Insert 하고자하는 key 가 이미 존재하는지 판단

이미 존재하는 경우 Insert 하지않고 원래의 root 를 그대로 return 함.

존재하지 않는 경우 key 값을 담은 새로운 record를 만들어 그 record 의 포인터를 Tree 에 삽입하기 위해 변수에 저장함.

2) Insert 하려는 Tree 가 존재하는지 판단 (root 가 NULL 인 경우)

Tree 가 존재하지 않는 경우 저장한 key 와 pointer(record *) 을 가지는 노드를 root 로 하는 새로운 tree를 만들어 return 함.

Tree 가 존재하는 경우 새로 만들 node를 tree에 삽입하기 위한 다음과정을 진행함.

3) key값을 담을 공간이 이미 존재하는지 판단

존재하는 경우 그 공간에 record pointer을 담고 tree 를 return

존재 하지 않는 경우 insert_into_node_after_splitting

Delete operation

Key_record 에 key에 해당하는 record 의 pointer 을 담고, key_leaf 에는 key에 해당하는 node 의 pointer을 담는다.

Master Delete Function


pagenum_t delete(int key) {

    int64_t key_leaf;
    char * key_value = find(key);


    key_leaf = find_leaf(key);
    if (key_value != NULL && key_leaf != NULL) {
        key_leaf = delete_entry(key_leaf, key, key_value);
    }
    return key_leaf;
}

위 함수에서 주요 역할은 실질적인 delete 를 실행하는 delete_entry 함수를 호출하는 것이다.

Delete Entry Function


pagenum_t delete_entry(pagenum_t n, int64_t key, char value[120] ) {

    int min_keys;
    pagenum_t neighbor;
    page_t * neighborP = calloc(1,PAGESIZE); 
    int neighbor_index;
    int k_prime_index, k_prime;
    int capacity;
	page_t* parentP = calloc(1,PAGESIZE);

	page_t * nP = calloc(1,PAGESIZE);
    n = remove_entry_from_node(n, key, value);

    
print_tree();
    if (n == off_to_num(headerP->root_off)) 
        return adjust_root(rootP);

	file_read_page(n,nP);

    min_keys = nP->is_leaf ? (cut(order - 1))/2 : (cut(internal_order) - 1)/2;


    if (nP->num_keys >= min_keys)
        return off_to_num(headerP->root_off);

    neighbor_index = get_neighbor_index( n );
    k_prime_index = neighbor_index == -2 ? 0 : neighbor_index+1;
    file_read_page(off_to_num(nP->parent),parentP);
    k_prime = parentP->branches[k_prime_index].key;

    neighbor = neighbor_index == -2 ? off_to_num(parentP->branches[0].child_off) : 
        off_to_num(parentP->branches[neighbor_index].child_off);

    capacity = nP->is_leaf ? order : internal_order - 1;

    file_read_page(neighbor,neighborP);
    
    // Coalescence.
print_tree();
    if (neighborP->num_keys + nP->num_keys < capacity)
        return coalesce_nodes(n, neighbor, neighbor_index, k_prime);

    //Redistribution.

    else
        return redistribute_nodes(n, neighbor, neighbor_index, k_prime_index, k_prime);
}

Delayed Merge의 구현

일반적인 merge 는 order/2 에 해당하는 key의 최소 수 (minimum number of keys) 에 도달하면 수행하도록 설계된다. 하지만, 이렇게 설계된 merge는 성능저하의 원인이 될 수 있다.

Insertion 에서 일어나는 Split operation 역시 키의 갯수가 order/2 에 도달하면 일어나게 되어있다. Spllit Operation 이나 Merge Operation 둘은 cost가 높은 operation 이기 때문에 호출을 적게하면 좋지만, 이렇게 설계된 경우 number or key가 order/2 근처에서 늘어나고 줄어들고를 반복하게 되면 불필요한 split과 merge operation이 반복되게 된다.

이러한 문제를 해결하기위해 다음과 같은 구현 방식을 채택하였다.

Delayed Merge 구현 형식

  min_keys = nP->is_leaf ? (cut(order - 1))/2 : (cut(internal_order) - 1)/2;

Delete Operation 에만 한해 min_keys 의 값을 기존 order/2 에서 order/4 정도로 수정하였다. 즉, key의 갯수가 Delete로 인해 order 의 절반으로 떨어지더라도 1/4 수준으로 떨어지기 전까지는 별다른 redistribution 이나 coalescence 와 같은 작용 없이 그대로 수용한다는 것이다.

이러한 방식으로 불필요한 split과 merge 를 줄이는 delayed merge 를 구현할 수 있다.

Overall Call Path of Delete

1) Key를 가진 record 나 node가 있는지 판단

없는 경우 다른 변화 없이 tree를 return 한다.

있는 경우 delete_entry 함수를 호출한다.

Delete_entry 함수에서 Key_leaf 에 담긴 key_record를 제거한다.

2) Key_leaf 가 root 인지 판단.

Root 인 경우 adjust_root 함수 호출 key_leaf 가 empty root 라면 delete 할게 없으므로, 그냥 return.

Empty root가 아니라면 first child 를 새로운 root로 만듦. 자식이 없다면 NULL return

Root 가 아닌 경우 계속 진행

3) Key_leaf 를 삭제한 이후 node를 보존하기 위해 node의 최소크기를 결정

Leaf node 인 경우 leaf page 의 크기에 맞춰 cut(order – 1)

Internal node 인 경우 interal page 의 크기에 맞춰 cut(order)-1

4) Delete 한 이후 tree를 유지할 조건을 만족하는지 판단

만족할 경우 Tree를 return 하고 마무리.

만족하지 않을경우 Tree 구조의 변화를 시도

5) Get_neighbor_index(n)을 통해 neighbor index를 얻고 neighbor 과 합쳐질 수 있는지 판단. ( 두 node를 합쳤을 때 key의 개수가 capacity를 넘어가지 않는지 판단 )

합칠 수 있는 경우 coalescence_nodes 함수 호출

합칠 수 없는 경우 redistribute_nodes 함수 호출

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

Split

Split 은 Tree 에 새로운 node 를 삽입할 때 insert_into_node_after_splitting 함수가 실행되면서 이루어 진다.

Splitting Function Code


pagenum_t insert_into_node_after_splitting(pagenum_t old_node, int left_index, 
												int64_t key, pagenum_t right) {

	file_read_page(0,(page_t*)headerP);
	
    int i, j, split, k_prime;
    page_t * new_nodeP = (page_t *) calloc(1,PAGESIZE);
    pagenum_t new_node;
	page_t * child = (page_t *) calloc(1,PAGESIZE);
    
	int64_t temp_keys[internal_order];
	off_t temp_off[internal_order];
	
	file_read_page(off_to_num(headerP->root_off),rootP);
	
	page_t * old_nodeP = (page_t *) calloc(1,PAGESIZE);
	file_read_page(old_node,old_nodeP);
	
	page_t * rightP = (page_t *) calloc(1,PAGESIZE);
	file_read_page(right,rightP);

    for (i = 0, j = 0; i < old_nodeP->num_keys; i++, j++) {
		if (j == left_index + 1) j++;
		temp_off[j] = old_nodeP->branches[i].child_off;
	}

	for (i = 0, j = 0; i < old_nodeP->num_keys; i++, j++) {
		if (j == left_index + 1) j++;
		temp_keys[j] = old_nodeP->branches[i].key;
	}

	temp_keys[left_index + 1] = key;
	temp_off[left_index + 1] = num_to_off(right);
 
    split = cut(internal_order-1);
    new_node = make_node();
    file_read_page(new_node,new_nodeP);
    
    old_nodeP->num_keys = 0;
    
    for (i = 0; i < split; i++) {
        old_nodeP->branches[i].key = temp_keys[i];
        old_nodeP->branches[i].child_off = temp_off[i];
        old_nodeP->num_keys++;
    }
        
    new_nodeP->ex_off = temp_off[split];
	k_prime = temp_keys[split];
	new_nodeP->num_keys = 0;

	for (i = split + 1, j = 0; i < internal_order; i++, j++) {
		new_nodeP->branches[j].child_off = temp_off[i];
		new_nodeP->branches[j].key = temp_keys[i];
		new_nodeP->num_keys++;
	}
    
    new_nodeP->parent = old_nodeP->parent;
    for (i = 0; i <= new_nodeP->num_keys; i++) {
    	file_read_page(off_to_num(new_nodeP->branches[i].child_off),child);
        child->parent = num_to_off(new_node);
        file_write_page(off_to_num(new_nodeP->branches[i].child_off),child);
    }
    file_write_page(new_node,new_nodeP);
    file_write_page(old_node,old_nodeP);
    file_write_page(right,rightP);
    
    free(new_nodeP);
    free(child);
    free(old_nodeP);
    free(rightP);

    return insert_into_parent(old_node, k_prime, new_node);
}

Overall Call Path

  1. Split 을 하기 위해 우선 새로운 key와 pointer 을 받은 후, key 값과 pointer 값을(새로운 값들을 포함하여) 담는 이루어진 임시 배열을 만든다.  Temp_pointer[j] = old_node->pointers[i]; | temp_keys[j] = old_node->keys[i];

  2. 이후, 새로운 노드를 만들고 배열의 키와 포인터를 절반으로 나누어 절반은 기존의 노드에 복사하고, 나머지 절반은 새로운 노드에 복사한다.  Cut(order) 을 통해 어디서 나눌지 결정 하여 split 에 담고, 0 ~ split – 2 까지는 기존의 old_node 에, split -1 ~ order -1 까지는 new_node 에 나누어 담는다.

새 노드의 parent 도 기존 노드의 parent 와 동일하게 설정하고, Split-1 에 담긴 key 를 대표키로 정한다.

  1. Insert_into_parent 함수를 통해 기존 노드는 왼쪽에, 새로운 노드는 오른쪽에 두어 split 한다.  기존 노드( left ) 의 parent 가 존재하지 않다면 insert_into_new_root 를 통해 key 를 root로 하는 새로운 tree에 insert 한다.  만약에 parent 에게 split 한 것을 저장 할 수 있는 left_index가 남아있다면 그곳에 split된 노드를 저장한다.  새로운 node를 넣을 자리가 없다면 parent 에 대해서도 split 을 진행한다.

새 노드의 key 값에 해당하는 자리가 없다면 split 이 일어난다. Split 이 일어나다가 parent 에게 split 된 node를 담을 수 있는 공간이 있다면, 그곳에 split 된 것을 넣고, 그렇지 않다면 parent 에 대해서도 공간이 생길 때까지 split을 한다. 만약 root 까지 split 해야 한다면, 대표키로 지정한 노드를 root로 하는 새로운 Tree 를 만든다.

Merge – Coalescence

노드의 key의 개수가 매우 적어지면 효율을 위해 merge를 진행한다.

( n->num_keys < min_keys ) 를 만족하는 경우.

Coalescence Function code


pagenum_t coalesce_nodes(pagenum_t n, pagenum_t neighbor, int neighbor_index, int k_prime) {
    int i, j, neighbor_insertion_index, n_end;
    pagenum_t root;
	page_t * nP = calloc(1,PAGESIZE);
	file_read_page(n,nP);
	page_t *neighborP = calloc(1,PAGESIZE);
	file_read_page(neighbor,neighborP);
	pagenum_t temp;
	page_t* tempP = calloc(1,PAGESIZE);

    if (neighbor_index == -2) {
    	file_write_page(neighbor,nP);
    	file_write_page(n,neighborP);
    	file_read_page(neighbor,neighborP);
    	file_read_page(n,nP);
    }

    neighbor_insertion_index = neighborP->num_keys;
    
    if (!nP->is_leaf) {

        neighborP->branches[neighbor_insertion_index/*-1*/].key = k_prime; 
        neighborP->num_keys++;


        n_end = nP->num_keys;

        for (i = neighbor_insertion_index + 1, j = 0; j < n_end; i++, j++) {
            neighborP->branches[i].key = nP->branches[j].key;
            neighborP->branches[i].child_off = nP->branches[j].child_off;
            neighborP->num_keys++;
            nP->num_keys--;
        }

        neighborP->branches[i].child_off = nP->branches[j].child_off;


        for (i = 0; i < neighborP->num_keys + 1; i++) {
            temp = neighborP->branches[i].child_off;
            file_read_page(temp,tempP);
            tempP->parent = num_to_off(neighbor);
            file_write_page(temp,tempP);
        }
    }


    else {
        for (i = neighbor_insertion_index, j = 0; j < nP->num_keys; i++, j++) {
            neighborP->records[i].key = nP->records[j].key;
            strcpy(neighborP->records[i].value,nP->records[j].value);
            neighborP->num_keys++;
        }
        strcpy(neighborP->records[order-1].value,nP->records[order-1].value);
    }
	file_write_page(n,nP);
	file_write_page(neighbor,neighborP);
	
    root = delete_entry(off_to_num(nP->parent), k_prime/*, nP->value*/);
    free(nP);
    free(neighborP);
    free(tempP);
    return root;
}

옆 노드의 키의 개수를 확인하여 옆 노드와 합쳤을 때 capacity를 넘어 서지 않는다면 coalescence, 넘어 선다면 redistribution 해야한다.

  1. 합쳐질 노드가 왼쪽 끝에 있다면 그 왼쪽 끝을 없애고 오른쪽으로 옮긴다.

  2. Neighbor 에 key 들을 옮기기 위해 neighbor 에 다음 키가 들어갈 수 있는 index 를 negibor_insertion_index에 저장한다.

  3. n 이 leaf node 가 아니라면 neighbor 의 마지막 key ( keys[neighbor_insertion_ index] ) 및 pointer 을 대표로 지정한 후 그 뒤에 n 의 key 들을 집어넣는 과정을 진행 그리고 neighbor 에 삽입된 node 들이 neighbor을 부모로 가지도록 설정.

  4. Leaf node 라면 neighbor에 key 와 pointer 들을 neighbor에 넣고, 바뀐 neighbor 의 마지막 pointer이 없어진 노드의 오른쪽 노드를 가리키도록 한다.

  5. Delete_entry를 실행하고 root를 return 한다.

Merge – distribution

Neighbor 노드로부터 임으로 key, pointer 쌍을 가져와 더 이상 key가 부족하지 않도록 만드는 과정이다.

Redeistribution Function Code


pagenum_t redistribute_nodes(pagenum_t n, pagenum_t neighbor, int neighbor_index, 
        int k_prime_index, int k_prime) {  

	page_t* nP = calloc(1,PAGESIZE);
	file_read_page(n,nP);
	page_t* neighborP = calloc(1,PAGESIZE);
	file_read_page(neighbor,neighborP);
	
    int i;
    int tmp;
    page_t * tmpP = calloc(1,PAGESIZE);
	page_t * parentP = calloc(1,PAGESIZE);

    if (neighbor_index != -2) {


        if (!nP->is_leaf) {
        	for (i = nP->num_keys; i > 0; i--) {
            nP->branches[i].key = nP->branches[i - 1].key;
            nP->branches[i].child_off = nP->branches[i - 1].child_off;
       		 }
			nP->branches[0].child_off = nP->ex_off;
            nP->branches[-1].child_off = neighborP->branches[neighborP->num_keys].child_off;
            tmp = nP->branches[-1].child_off;
            file_read_page(tmp,tmpP);
            tmpP->parent = num_to_off(n);
            neighborP->branches[neighborP->num_keys].child_off = 0;
            nP->branches[0].key = k_prime;
            file_read_page(off_to_num(nP->parent),parentP);
            parentP->branches[k_prime_index].key = neighborP->records[neighborP->num_keys].key;
        }
        else {
        	for (i = nP->num_keys; i > 0; i--) {
            nP->records[i].key = nP->records[i - 1].key;
            strcpy(nP->records[i].value, nP->records[i - 1].value);
        	}
        	strcpy(nP->records[0].value, neighborP->records[neighborP->num_keys - 1].value);
            neighborP->records[neighborP->num_keys-1].value[0]='\0';
            nP->records[0].key = neighborP->records[neighborP->num_keys - 1].key;
            file_read_page(off_to_num(nP->parent),parentP);
            parentP->records[k_prime_index].key = nP->records[0].key;
        }
    }

    else {  
        if (nP->is_leaf) {
            nP->records[nP->num_keys].key = neighborP->records[0].key;
            strcpy(nP->records[nP->num_keys].value,neighborP->records[0].value);
			file_read_page(off_to_num(nP->parent),parentP);
            parentP->records[k_prime_index].key = neighborP->records[1].key;
        }
        else {
            nP->branches[nP->num_keys].key = k_prime;
            nP->branches[nP->num_keys + 1].child_off = neighborP->branches[0].child_off;
            tmp = nP->branches[nP->num_keys + 1].child_off;

            file_read_page(off_to_num(tmp),tmpP);
            file_read_page(off_to_num(tmpP->parent),parentP);
            file_read_page(off_to_num(parentP->parent),parentP);
            parentP->branches[k_prime_index].key = neighborP->branches[0].key;
        }
        for (i = 0; i < neighborP->num_keys - 1; i++) { 
            neighborP->records[i].key = neighborP->records[i + 1].key;
            strcpy(neighborP->records[i].value,neighborP->records[i+1].value);
        }
        if (!nP->is_leaf)
			neighborP->branches[i].child_off = neighborP->branches[i + 1].child_off;
    }

    nP->num_keys++;
    neighborP->num_keys--;

	file_write_page(n,nP);
	file_write_page(neighbor,neighborP);
	file_write_page(off_to_num(nP->parent),parentP);
	
	free(nP);
	free(neighborP);
	free(tmpP);
	free(parentP);
	
    return off_to_num(headerP->root_off);
}

  1. 노드의 왼쪽에 neightbor 이 있는경우 neighbor 의 마지막 key, pointer 쌍을 노드의 왼쪽 끝으로 가져온다.

  2. 노드가 가장 왼쪽에 있다면 neighbor의 key,point 쌍을 노드의 오른쪽으로 붙인다.

  3. 노드의 num_key를 1 키우고, neighbor은 1 줄인 후, Tree 를 return 한다.

Project 5

Greeting. & Will be completed after the end of the course