Skip to content

Project3

Jump to bottom
iQuQi edited this page Jul 27, 2021 · 1 revision

B+tree design report

0.Project3

  • 이번 프로젝트는 이전의 디스크 기반의 비쁠 트리 위에 버퍼 매니저 계층을 추가하여 구현하는 것이 목적이다.

  • 디스크에 직접적으로 읽기/쓰기를 하는 것은 상당한 시간이 소요된다.

  • 걸리는 시간을 단축하기 위해 버퍼라고 불리는 메모리에 페이지들을 한번 읽어와서 저장해두고 사용하여 상위 계층으로 전달하고 이후 필요에 의해 디스크로 저장된다.

  • 이번 프로젝트에 추가된 새로운 점은 하나 이상의 테이블을 다루며 각각은 고유의 아이디를 갖는다는 것이다.

1.Buffer

1)버퍼프레임 구조

  • 버퍼는 페이지를 읽어와서 저장하는 페이지 공간과 버퍼 매니저가 프레임들을 관리할 때 필요한 추가 정보들로 이루어져 있다.

  • 페이지 공간에는 이전에 만들어 두었던 페이지 구조체를 사용하여 공간을 할당하여 준다.

  • 추가적으로 필요한 정보는 다음과 같다.

<1>테이블 아이디와 페이지 넘버 : 읽어온 페이지의 테이블 아이디와 페이지 넘버를 저장한다.

<2>next/pre : LRU 더블 링크드 리스트 구현 시 필요한 변수이다. 비어 있지 않고 사용중인 프레임들은 모두 LRU(가장 사용한지 오래된 페이지를 Drop하는 방식)리스트에 들어가 있으며 가장 최근에 읽어온 페이지를 가장 앞쪽으로 넣는다. 즉 Tail이 Drop 대상이다.

<3>is dirty/is pinned : 수정된 경우 isdirty 설정 해주고 사용중인 경우는 ispinned를 설정해준다.

2)버퍼 매니저 구조

  • 버퍼 매니저는 4가지 정보가 필요하다

<1> 테이블의 정보 : 테이블 구조체 배열을 생성하여 관리한다. 테이블 구조체에는 파일디스크립터 정보, 테이블 아이디, 파일명, open/close 상태 정보가 있다. 또한 현재 테이블 리스트에 올라와 있는 테이블의 개수와 저장가능한 테이블의 최대개수 정보도 포함한다.

<2> 프레임 배열 : 프레임 구조체들을 저장한다.

<3> 프레임배열의 상태 : 총 용량과 현재 사용량 정보를 저장한다.

<4> LRU 리스트 : LRU리스트의 head/tail를 가리키는 변수를 포함한다.

3)기능

  • init db : 처음 프로그램 실행 시 버퍼를 초기화 시켜준다.

  • open table : 사용자에게 파일명을 입력 받아 테이블을 열어준다. 그 파일명이 버퍼매니저의 테이블 리스트에 올라와 있는 경우 저장 되어있는 고유 아이디를 사용하며, 새로 입력된 파일명인 경우 고유 아이디를 부여하고 테이블 리스트에 올려준다.

  • close table : 받아온 테이블 아이디에 부합하는 테이블을 닫아준다. 파일을 close하기 전에 버퍼위에 올라와 있던 해당 테이블의 페이지들을 내려주는데, Dirty인 경우 write 후 Drop한다.

  • shutdown db : 테이블 리스트에 올라와 있는 모든 테이블을 close한다.

  • page scan : 받아온 테이블 아이디와 페이지 넘버 정보로 먼저 해당하는 페이지가 버퍼위에 이미 올라와있는지 확인한다. 그렇지 않은경우 페이지를 디스크에서 읽어오는데 버퍼가 가득찬 경우 LRU리스트의 Tail Frame을 Drop함수로 비운다.

  • page load : 페이지를 프레임으로 올려온 후 LRU 리스트에 연결시켜준다.

  • page drop : LRU 리스트를 수정해준 뒤 프레임을 Drop한다. 대신 dirty 인 경우 write를 먼저 진행한다.

  • pin check : 버퍼가 모두 pinned되어있는지 확인한다.

  • set/clear pinned : 버퍼 프레임의 사용 여부에 따라 ispinned을 각각 1,0으로 변경하여 상태를 설정한다.

  • set/clear dirty : 버퍼프레임의 수정 여부에 따라 isdirty를 각각 1,0으로 변경하여 상태를 설정한다.

  • delete/find/insert : 이전의 프로젝트에서의 기능과 동일하나 다른점은 해당 작업을 수행할 때 버퍼에 올라와있는 프레임을 통해 삭제/탐색/삽입 작업을 진행하는 것이다.

  • file allcoate page: 새 페이지가 필요하면 새 프레임을 할당하여 free page로 사용한다. 내부 페이지공간의 free page 정보를 수정해줘서 free page 리스트에 연결시켜준다.

  • file free page: free리스트로 해당 페이지를 넣어준다.

2.Disk

  • 이전의 경우 find/delete/insert 시 매번 직접적으로 디스크에서 read 함수를 통해 페이지를 읽어오고/수정한 후 디스크에 다시 내려 저장하는 방식이었으나 이번 프로젝트에서는 우선 처음 버퍼에 올릴 때 read함수를 사용하고 모든 수정과정은 버퍼 위에서 일어나도록 한다.

  • 수정이 끝난 후 버퍼의 용량이 가득차서 프레임을 비워줘야 할 때나 테이블을 닫을 때 Dirty된 페이지들을 내려서 저장시에만 write 함수 호출을 통해 직접적으로 써준다.

  • file_read_page / file_write_page : 이전의 함수와 달라진 점 없이 동일한 기능을 수행한다.

Clone this wiki locally