Project Gaia/계획설계

1. key 순차 파일 A안

1.1. 세부설명
1.2. 작동방식
1.3. 추가필요사항

2. B안

2.1. 키 순차화일

2.1.1. 1. 레코드 입력 - creat_s()
2.1.2. 2. 레코드 검색 - retrieve_s()
2.1.3. 3. 레코드 삽입 - insert_s()
2.1.4. 4. 레코드 삭제 - delete_s()
2.1.5. 5. 레코드 교체 - replace_s()
2.1.6. 6. 조각모음 - restruct_s()

3. 구현

[edit]

1. key 순차 파일 A안 ¶

Page 논의에 관하여
우선 이번 우리 AP의 절대 조건을 알아보면,
1. 속도가 빨라야 한다.
2. 페이지가 IO의 기본 단위이다.
3. 가변길이 레코드로 한다.

~cpp 
       ---------------------------------------------------------
      -  페이지ID   |  첫RecordID  |  FreeSpace  |  ptrToFree  -
      -  (Word)    |  (Word)      |  (Word)     |  (Word)     _
      ---------------------------------------------------------
      -  Record          |  Record  |  Record.....            -
      -  (Record Size)   | (R-Size) | (R-Size)                -
      ---------------------------------------------------------
      -         비신장 가변길이 레코드  &                        -
      -                                    FreeSpace          -
      ---------------------------------------------------------
      -      - ... -  Length  -  Length  - Length   - Last_   -
      -      - ... -  ID      -  ID      - ID       - Slot_   -
      -      - ... -  Pointer -  Pointer - Pointer  - Pointer -
      ---------------------------------------------------------

[edit]

1.1. 세부설명 ¶

페이지 ID등 일반적인 크기 단위를 Word로 하여 충분한 크기를 제공하고 속도를 보장받고자 하며,,
ID를 보다 빠르게 접근하기 위해서..
1. Slot자체에 ID를 포함시켰고,
  DeleteMe ID 포함시 의미 궁금
2. 페이지에도 첫 ~cpp RecordID를 접근할 수 있도록 하였으며,
불필요할 것으로 판단되는 ~cpp NumberOfRecord 값은 오버헤드차원에서 삭제처리하였고,,
LSP(Last Slot Pointer)는 슬롯에 있는 ID를 B-Search하기 위해서 가장 안쪽 슬롯의 위치를 가리키도록 함.

또한 슬롯을 추가할 경우에 추가할 위치를 포인터로써 바로 접근 할 수 있을것임.
기타 세부적인 수정은 보는이의 판단을 요구하고 있음.

[edit]

1.2. 작동방식 ¶

어떤 레코드를 삽입/삭제/검색을 하고자 포인터를 찾고자 할 경우에..
제일 먼저 그 레코드의 ID와 페이지 ID를 비교하여.. 페이지를 찾게 되고,
이에 슬롯에 있는 ID와 비교한 후,,
삭제/검색시에 해당 포인터로 이동하여 세부수행
삽입의 경우.. ~cpp FreeSpace>Slot_Size+Record_Size와 비교후에 수행

[edit]

1.3. 추가필요사항 ¶

페이지ID, 페이지 위치, 첫~cpp RecordID를 찾거나 가는데 IO 수행이 너무 많이 필요하다.
왜냐면,, 비교를 하기위해서 페이지를 적어도 한번은 읽어야 하기 때문에..
이에 마스터페이지(페이지들의 정보를 저장하고 있는 페이지)를 따로 선언해야만 한다.
그렇게 된다면, 첫~cpp RecordID까지도 마스터페이지가 관리하도록 할 것임.
변수가 적을수록 좋다. (관리가 적을수록 빠르다?!)

[edit]

2. B안 ¶

공통

화일생성 - 레코드 10000개, unsorted 화일 생성 (생성 여부 확인을 위해 화면 출력 가능하도록 구현)

[edit]

2.1. 키 순차화일 ¶

키 순차화일 구현을 위한 프로세스

[edit]

2.1.1. 1. 레코드 입력 - creat_s() ¶

키 순차화일은 키 순서로 정렬된 화일을 말한다.(교재122p부터) 여기서 키는 primary key(첫번째 필드)가 된다.
unsorted 레코드를 sort하면서 page 단위 메모리에 적재를 하되, 이때 정렬 대상 레코드를 메모리에 모두 올려서 정렬하지 않고, memory size 10인 자연선택(교재155p)을 이용함. 여기서 memory size 10이라는 것은 10개의 레코드를 올릴 수 있는 공간을 말 하고, 가변 길이 레코드일 경우 실제 사이즈는 변할 수 있다. 자연선택 이후, m-원 다단계 합병(교재166p).
정렬된 레코드를 page(4KB) 단위로 입력, page에는 header와 slot이 차지하는 공간을 제외한 크기만큼 레코드를 저장할 수 있다. 레코드를 page에 입력할 때 비신장 가변길이 저장 방법을 사용, 입력될 레코드가 page의 남은 공간보다 클 경우 다음 page에 입력된다.

[edit]

2.1.2. 2. 레코드 검색 - retrieve_s() ¶

레코드의 효율적인 검색or삽입or삭제를 위해서는 page의 구조, page 접근을 위한 구조가 잘 구성되어야 한다.
page 접근을 위해 master page를 둔다. master page는 page들 중 가장 앞에 위치한다.

master page는

① page ID,

② page 내 레코드 중 가장 큰 key값,
③ 현재 저장된 전체 레코드 수
④ 페이지 수 등을 저장한다.

master page에 |②|①| 로 이루어져 있는 table을 둔다.
key값이 20인 레코드를 검색하고 싶다면, master page의 table을 보고 해당 page ID를 찾은 다음, page 내부에서 검색하게 된다.
"page 내부에서 검색하는 것에 대해 논의해볼 필요가 있음."

[edit]

2.1.3. 3. 레코드 삽입 - insert_s() ¶

레코드는 무조건 화일의 끝에 삽입한다.
master page의 page 수를 읽고 가장 마지막 page로 간 다음, page header의 freespace size를 삽입 예정 레코드의 크기와 비교하여, 만약 해당 page에 충분한 공간이 있다면 그대로 추가 입력, 충분한 공간이 없다면 다음 page를 생성하고 넣어주는 비신장 가변길이 방법을 이용한다.

'비신장'에 의해 page에 어중간하게 남는 공간에는 null flag를 둔다. 이후, 조각모음.

[edit]