데이터베이스의 파일 저장 구조로 static index 구조를 사용하면 오버플로우 체인 같은 문제의 발생을 피하기 어렵다.(ex. ISAM)
그러므로 insert, delete가 좀 더 매끄럽게 일어날 수 있도록 하는 dynamic index 구조인 B+ 트리를 사용하여 보자.

• tables

• 테이블을 관리하기 위한 struct 구조

• buffers

• 페이지 수정을 IO가 아닌 MEMORY에서 일어나게 하기 위한 자료구조

• disks

• 데이터를 파일 형태로 저장

• views

• insert, delete, update를 수행하기 위한 함수

헤더페이지에서는 각종 DB의 정보 즉, metadata를 저장한다.

• root 페이지의 offset도 가지고 있으며, 첫 free page의 offset또한 가지고 있다.
• 적절한 상황에 expand를 하기 위하여 전체 page number 와 전체 free page number또한 가지고 있다.

• b+트리에 페이지를 할당해줄 때마다 새로 페이지를 새로 생성 해준다면 이때, 페이지 ALLOC이 일어날 때마다 페이지를 만드는 IO는 너무 크기 때문에 이를 줄이기 위해 free페이지를 미리 만들어주고 이를 헤더 페이지에서 미리 연결해 놓아준다.

• 확장성: FreePage를 전부 다 쓰고 다시 추가하는 경우, 추가하는 동안에 다시 alloc이 일어난다면 expand가 전부 일어날 때까지 alloc이 기다려야하기 때문에 문제가 생긴다. 따라서, (free page의 갯수) / (전체 페이지의 갯수) < 0.20 일때, 미리 확장을 시킨다.

• free page는 다음 free page는 다음 free page의 offset을 가지고 있다.
  

free page는 확장을 할때, 포인팅을 하기전에 공간을 파일에 공간을 미리 잡아주고(IO) 마지막에 이미 할당되어 있는 free page와 header page에 연결해준다.

실질적으로 데이터가 가치있는 데이터가 저장되는 페이지이다. key(8byte) + value(120byte) = entry(128byte) 이다.
그림과 같이 128 ~ 4096 이므로 총 32개의 entry를 담을 수 있고 120 ~128까지의 8byte에는 자신의 sibling즉, 자신 옆의 page의 offset을 저장한다.

LeafPage를 찾기 쉽게 해당 key에 대한 offset으로 entry가 이루어진 page이다. key 8byte offset 8byte로 총 16byte 이기 때문에 그림과 같이 총 249개의 entry를 담을 수 있다. (form 120 ~ 128에 offset만 1개를 더 담을 수 있으므로 offset은 총 249)

• key를 입력받으면 해당하는 value를 찾는 function이다.
• 인자로 tid, key, str을 받는다.
• 동작: key에 해당하는 value를 찾아서 str에 복사한다.

• key와 value를 입력 받으면 이를 B+트리 구조의 Disk에 넣어준다.
• 인자로 tid, key, value를 받는다.

• key를 입력 받으면 이를 찾아서 B+트리 구조의 Disk에서 찾아서 제거 한다.
• 인자로 tid, key를 받는다.

• Freepage가 부족한 경우 호출하는 function이다.
• 인자로 tid와 확장할 size를 받는다.

• FreePage에서 헤더가 가르키고 있는 페이지를 가져온다.
• tid를 인자로 받는다.
• return값으로 해당 freepage의 offset을 출력한다.
• alloc을 다해준 상태에서 EXTENDPERCENT(== 0.20) >= (free page 수)/(총 페이지 수) 일 경우 Extend를 호출한다.
  

• 지워진 페이지를 현재 헤더 페이지가 가르키는 freePage를 가르키도록 하고 헤더 페이지의 next free page는 이 지워진 페이지를 가르키도록 한다.
• 인자로 tid, offset을 받는다.

이 테스트가 안전하게 돌아간 것이 확인되었다.