-
Notifications
You must be signed in to change notification settings - Fork 0
Project2_milestone2
프로그램 실행 시 가장 먼저 사용자에게 path name을 입력 받는다.
해당하는 파일을 open_table() 함수를 이용하여 열어준다.
open table 함수 안에서는 해당 이름의 파일이 존재하지 않을 시 새로 생성한 후 헤더를 만들어준다.
해당 이름의 파일이 존재하는 경우 그 파일을 열어준다.
사용자에게 insert,delete,find,print,quit 이 다섯개의 명령을 입력받는다.
이 후 db_insert,db_delete,db_find,print_tree 중에서 해당되는 함수를 호출한다.
quit 명령의 경우 close()로 파일을 닫아준다.
leaf/internal page를 새로 만들 때 free page list에서 page를 가져와서 할당해준다.
현재 free page가 하나도 없다면 15개의 free page를 더 생성해준 후 새 page를 할당해준다.
사용되고 있던 page를 free page list에 넣어준다.
page number를 넘겨받아서 해당하는 page를 읽어준다.
또한 안에서 오류체크도 같이하여 제대로 읽어졌는지 검사한다.
page number를 넘겨받아서 해당하는 page에 써준다.
또한 안에서 오류체크도 같이하여 제대로 쓰여졌는지 검사한다.
root 페이지를 읽어온 후 큐를 사용하여 root부터 시작해서 밑으로 내려가서 받아온 키가 들어갔을 만한 leaf 페이지를 찾아온다.
받아온 leaf 페이지에 찾는 키가 들어있다면 해당하는 value 값을 저장해준다.
찾는 키가 없다면 -1을 리턴한다.
키를 삽입하기전 find 함수를 이용하여 해당 키가 이미 있는지 확인한다.
이미 존재한다면 삽입은 불가능하다.
키와 value를 넣을 리프 페이지를 찾아온다.
만약 첫 삽인인 경우 start _new_tree 함수를 호출하여 새 루트 페이지를 생성한다.
-받아온 리프 페이지에 넣을 자리가 남아 있는 경우 insert_into_leaf 함수를 호출한다.
이 후 삽입 위치를 찾아 자리를 밀어서 비워준 후 해당 키와 value를 write한다.
-남은 자리가 없다면 insert_into_leaf_after_spliting 함수를 호출한다.
리프 페이지를 새로 받아와서 반으로 나눠서 넣어준다. 수정 후 자신의 왼쪽페이지를 가리키는 right_left 변수도 알맞게 수정 해준다.
옮겨서 없어진 칸들을 초기화 시켜준 후 새로 만들어준 리프 페이지의 부모를 원래 페이지의 부모로 설정해준다.
이 후 insert_into_parent함수 호출을 통해 부모에 새 키를 복사해서 올려준다.
만약 이 때 부모가 없다면 (즉 자신이 루트였다면) insert_into_new_root 함수를 호출한다.
또한 만약 부모에 새 키를 넣을 자리가 없다면 다시 나눠줘야 하므로 insert_into_node_after_splitting함수를 호출한다.
부모에 새 키를 넣을 자리가 있다면 insert_into_node 함수를 호출한다.
부모쪽에 키를 넣을 자리가 있다면 단순히 해당하는 인덱스에 넣어주면된다.
키를 넣을 자리가 없다면 다시 반으로 나눠주는데 insert_into_leaf_after_splitting 함수와 유사하게 동작한다.
다른 점은 internal page의 경우 그 페이지의 child의 parent 재설정이 필요하며 key를 복사해서 올리는 것이 아닌 하나의 키를 그대로 위로 가져가버린다는 것이다.
또한 right_left(가장 왼쪽 페이지를 가리키는 변수)에 대한 조정도 필요한데 올린 키가 원래 가리키고 있던 child를 새로 만든 노드의 right_left가 가리키도록 변경해준다.
key prime을 부모에 올려주는데 만약 또 다시 부모가 키를 넣을 공간이 없다면 다시 나눠서 쪼갠다.
order을 만족할 때까지 위로 올라가면서 page를 쪼개준다.
find_page 함수 호출을 통해 받아온 키가 있을 페이지를 가져온다.
만약 그 페이지에서 해당 키를 발견한다면 delete_entry 함수를 호출하여 삭제를 진행한다.
해당 키를 발견하지 못한다면 -1를 리턴하여준다.
해당 키를 삭제한 이후 키가 0개가 되면 이웃 페이지와 합치는 작업이 필요하다.
합치기 전 합쳤을 때 용량이 초과되는지 확인해준 후 coalesce가 불가하면 redistribution을 진행한다.
이 후 merge를 해야하는 페이지가 leaf 인지 internal인지 판별한다.
합치는 방향은 항상 오른쪽에서 왼쪽이며(항상 '이웃'은 왼쪽) delay merge로 인해 키가 다 삭제되었을 때만 merge를 진행한다.
먼저 leaf 페이지인 경우
-해당 페이지가 가장 왼쪽 페이지가 아닌 경우 : 이웃의 right_left(자신의 오른쪽 이웃 페이지)를 현재 페이지의 right_left값으로 변경시켜준 후 해당 페이지를 free 해준다.
-그렇지 않은 경우 : 비어버린 왼쪽 페이지에 오른쪽페이지 정보를 다 옮겨온 후 위와 같은 작업을 해준다.
internal 페이지인 경우
이웃 쪽으로 정보들을 다 옮겨주고 자식들의 부모 재설정도 진행한다. 이후 비어버린 페이지를 free 해준다.
이 후 delete_entry함수 호출을 통해 부모에게서 삭제되어야 할 키를 삭제한다.
현재 비쁠트리는 delay merge를 구현하였고 모든 키가 삭제될 때까지 merge를 하지 않는다.
그러므로 leaf 페이지는 모든 정보가 삭제될 때 까지 merge를 하지 않게 되고 어떠한 경우에도 이웃과 합친 후 용량을 초과하는 일이 발생하지 않는다.
즉 redistribution는 internal 페이지에 대해서만 고려한다.
항상 merge는 오른쪽에서 왼쪽으로 일어난다.
이 때 internal page의 경우 키가 다 사라진다고 해도 right_left(가장 왼쪽 페이지를 가리킴)를 갖고 있으므로 이웃 페이지로 합쳐줘야 하는데 이웃 페이지에 공간이 없다면 '빌려오기'를 해야한다.
만약 현재 페이지가 가장 왼쪽 페이지여서 왼쪽 이웃이 존재하지 않는다면 오른쪽 이웃에게서 빌려오고 그렇지 않다면 왼쪽 페이지에서 빌려온다.
나와 이웃사이의 부모쪽의 키를 key prime이라고 하면 부모에게서 key prime을 빌려온후 그 자리를 이웃의 키로 채운다. 이후 리프인지 아닌지에 따라 child의 부모 재조정 또는 right_left 변수의 값 조정이 필요하다.
이웃의 비어진 칸을 초기화 시켜주고 당겨줘야 한다면 당긴다.