| English | 의미 |
|---|---|
| file organisation/faɪl ˌɔːɡənaɪˈzeɪʃn/ | 파일 조직 |
| access method/ˈækses ˈmeθəd/ | 접근 방식 |
| serial file/ˈsɪərɪəl faɪl/ | 직렬 파일 |
| sequential file/siːˈkwenʃl faɪl/ | 순차 파일 |
| key field/kiː fiːld/ | 키 필드 |
| direct access/daɪˈrekt ˈækses/ | 직접 접근 |
| sequential access/siːˈkwenʃl ˈækses/ | 순차 접근 |
| random file/ˈrændəm faɪl/ | 무작위 파일 |
은행 야근이 밤새도록 걸렸던 이유
- 1980년대까지 은행 계좌는 자기 테이프에 보관되었습니다. 테이프는 한쪽 끝에서 다른 쪽 끝으로만 읽을 수 있으므로, 당일 거래 내역은 밤새 정렬되고 전체 마스터 파일은 적용하기 위해 시작부터 끝까지 단 한 번 읽혀졌습니다.
- 오후 중간에 한 고객의 잔고를 문의하면 답은 다음과 같았습니다: "내일까지 기다리십시오." 은행이 제공할 수 있는 것은 컴퓨터의 속도보다 파일의 조직 방식이 결정했습니다.
- 디스크는 다른 조직 방식을 가능하게 했습니다: 키로부터 레코드의 위치를 계산하고那里跳跃去。这就是ATM机在一秒内做出反应的原因。
- 이 교훈은 파일 조직, 두 가지 접근 방법(access methods), 그리고 프로그램의 대부분이 수행하는 작업에 따라 선택하는 방법입니다.
세 가지 조직
- 직렬 파일(serial file) 은 추가된 순서대로 레코드를 유지하며, 정렬은 없습니다. 추가(appending)은 빠르지만, 검색(searching)은 시작에서부터 읽어야 합니다. 로그(logs) 및 감사 기록(audit trails)에 사용됩니다.
- 연속 파일(sequential file) 은 키 필드(key field)에 의해 정렬된 레코드를 유지합니다. 검색이 빠릅니다. 초기에 멈출 수 있거나 이분 탐색(binary-search)을 할 수 있기 때문입니다. 삽입(inserting)은 느립니다. 나중에 오는 레코드를 이동해야 하기 때문입니다. 일괄 업데이트(batch update)되는 마스터 파일에 사용됩니다.
- 임의(random) 또는 직접 접근(direct-access) 파일은 각 레코드를 레코드 키로부터 계산된 위치에 유지합니다. 보통 해시(hash)를 사용합니다. 키에 의한 조회(lookup)는 매우 빠르지만, 키 순서로 읽는 것은 불편합니다. 대규모 조회 표와 고객 계좌에 사용됩니다.
직렬: 도착 순서, 그 이상은 없습니다
연속: 같은 레코드들, 키 순서로
두 가지 접근 방법
- **순차 접근(sequential access)**은 파일의 시작점에서 원하는 레코드까지 읽습니다. 이는 직렬(serial) 파일에서 허용되는 유일한 접근 방식이며, **순차文件(sequential file)**이 배치 처리될 때 사용되는 방법입니다.
- **직접 접근(direct access)**은 이전 내용을 읽지 않고Known한 위치로 바로 이동합니다. 이는 랜덤(random) 파일을 읽는 방식이며, 키(key)의 위치를 알고 있거나 인덱싱되어 있을 경우 순차 파일도 직접 읽을 수 있습니다.
- 따라서 syllabus 매칭은 다음과 같습니다: 직렬 및 순차 파일에는 순차 접근을, 순차 및 랜덤 파일에는 직접 접근을 사용합니다.
랜덤: 키가 어디를 찾아야 하는지 알려줍니다
파일 접근 경로
저장소부터 프로그램으로 다시 돌아올 때까지 파일을 안전하게 따라감.
시리얼 파일(Serial file)은 레코드를 저장합니다:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
시리얼 파일은 도착 순서로 레코드를 유지하므로 추가는 빠르지만 검색은 느림. 시퀀셜 파일은 키에 의해 정렬됨.
각 파일 조직화를 레코드 저장 방식과 매칭하시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
시리얼 = 도착 순서; 시퀀셜 = 정렬됨; 랜덤 = 해시된 위치; 인덱스-시퀀셜 = 정렬 + 인덱스.
랜덤(직접 접근) 파일은 각 레코드를 배치합니다:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
키가 위치로 변환(보통 해시를 통해)되므로 단일 키 조회가 매우 빠름.
시리얼 파일과 시퀀셜 파일의 차이는 무엇인가?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
도착 순서 versus 키에 의한 정렬. 이 단일 차이가 시퀀셜 파일을 조기에 검색 가능하게 하고 삽입에는 느리게 만듦.
worked example: 조직 선택하기
-
- payslip program은 매달 employee-number 순서로 모든 employee record를 한 번씩 읽어 payslip을 생성합니다. 어떤 조직과 접근 방식이며, 그 이유는 무엇인가?*
- 순차적 조직과 순차적 접근: 모든 레코드를 처리하므로 점프하는 이점이 없으며, 키 순서로 저장하면 정렬 단계 없이 payslip이 순서대로 출력됩니다.
-
- ATM은 account number로 한 account를 1초 이내에 가져와야 합니다.* 랜덤 조직과 직접 접근: 위치가 account number에서 계산되므로 수백만 개의 레코드를 검색할 필요 없이 정확히 한 번의 읽기만으로 충분합니다.
-
- 웹 서버 앱은 요청마다 로그에 한 줄을 추가합니다.* 직렬: 추가만 중요하며, 직렬 파일의 끝부분에 추가하는 것이 가장 빠른 작업입니다.
시퀀셜 파일은 시퀀셜 접근과 직접 접근 모두로 읽을 수 있음.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
시퀀셜 접근은 시리얼 및 시퀀셜 파일을 지원하며, 직접 접근은 시퀀셜 및 랜덤 파일을 지원함. 오직 시리얼 파일만 하나의 방법에 제한됨.
랜덤 파일에서 계정을 하나 가져오는 단계를 순서대로 나열하시오.
난이도 3/5 · 200 코인 + 오늘 첫 완료 시 소액 보너스
전혀 검색이 일어나지 않음: 키는 위치로 변환되어 한 번만 읽힘. 최종 확인은 충돌을 포착함.
트레이드오프, 나란히 보기
| 직렬 | 순차 | 랜덤 | |
|---|---|---|---|
| 레코드 순서 | 추가된 순서 | 키로 정렬됨 | 키에서 계산됨 |
| 레코드 추가 | 빠름, 추가 | 느림, 레코드 이동 | 빠름, 슬롯이 비어있을 때 |
| 하나의 레코드 찾기 | 느림, 모두 읽음 | 빠름, 미리 멈출 수 있음 | 가장 빠름, 한 번 읽음 |
| 키 순서로 읽기 | 정렬 필요 | 자연스러움 | 정렬 필요 |
- 정답은 항상 **우선 작업(dominant operation)**에서 논증해야 합니다: 이 프로그램이 가장 많이做什么하는가?
시퀀셜 파일 조직화는 레코드를 차례대로 처리하기에 적합함.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
직접 접근은 단일 레코드 조회에 적합함.
각 상황을 그에 적합한 파일 조직화와 매칭하시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
추가만, 순서대로everything 처리, 또는 레코드 하나 조회: 지배적인 연산이 조직을 결정함.
worked example: 변경 사항 정당화하기
-
- 도서관의 책 파일은 직렬입니다. 특정 제목을 찾는 데 시간이 걸립니다. 변경 사항을 제안하고 정당화하십시오.*
- ISBN을 주소로 해시하여 랜덤 파일로 재조직하면, 전체 파일을 스캔하는 대신 한 번의 직접 읽기로 검색이 가능합니다.
- 도서관이 제목 순서로 카탈로그를 인쇄한다면, 제목에 따른 순차적 조직이 두 가지 모두를 합리적으로 처리할 수 있습니다: 카탈로그는 정렬이 필요 없고, 검색은 미리 멈추거나 이진 검색을 할 수 있습니다.
- 조직을 명시하고, 접근 방식을 명시하며, 문제에서 언급한 작업과 연결하십시오.
키 순서로 리포트를 생성하려면, 가장 좋은 파일 조직화는:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
시퀀셜 파일은 이미 키 순서이므로 시퀀셜로 읽으면 순서대로 된 리포트를 얻음.
파일 조직.program의 ____ 연산을 보는 것으로 선택됨.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
모든 조직은 어떤 데는 빠르고 다른 데는 느리므로, 가장 많이 수행되는 연산이 결정함.
키가 되어야 할 것, 그리고 해시가 실패하는 이유
- 직접 접근에는 키가 필요하며, 키는 하나의 레코드에 대해 유일성(unique) 을 가져야 합니다. 성(surname)은 키가 아닙니다. 고객 번호가 키입니다.
- **해시(hashing)**는 이 키를 하나의 연산으로 레코드 주소로 변환하여, 파일 크기가 아무리 커도 단일 읽기로 레코드에 도달할 수 있게 합니다.
- 서로 다른 두 개의 키가 같은 주소로 해시될 수 있습니다. 이를 충돌(collision) 이라고 하며, 이는 알고리즘의 결함이 아닙니다: 가능한 키의 수가 주소보다 많으면 불가피한 현상입니다.
- 만점 답안에서 제시하는 해결책은 오버플로우 영역(overflow area) 또는 공유하는 레코드 체인의 주소를 가리키는 포인터(pointer) 를 주소에 저장하는 것입니다. 따라서 충돌은 레코드 손실 대신 추가적인 한 번의 읽기 비용으로 발생합니다.
- 따라서 정직한 비교는 다음과 같습니다: 해시는 파일이 가득 차기 전까지는 거의 일정하게 접근 속도를 유지하지만, 충돌이 쌓이면 성능이 저하됩니다. 순차 접근은 절대 저하되지 않으나, 본래 빠르지 않았습니다.
두 레코드가 동일한 주소에 해시됨. 옳은 것은 무엇인가? 모두 선택하시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
분실된 것은 없음; 충돌은 추가 읽기 한 번을 요구함. 원칙적으로 피할 수 없음, 가능한 키가 주소보다 항상 많기 때문임.
놓칠 수 있는 점
- 직렬은 도착 순서이며, 순차는 키로 정렬된 것입니다. 이들은 동의어가 아니며, 시험에서 이 차이를 정확히 테스트합니다.
- 조직(organiation) 은 레코드가 배열되는 방식이며, 접근(access) 은 프로그램이 하나의 레코드에 도달하는 방식입니다. 문제는 하나 혹은 둘을 명시합니다.
- 순차 파일은 두 가지 접근 방법을 모두 지원하지만, 직렬 파일은 순차 접근만 지원합니다.
- "더 빠르기"가 아닌 우선 작업에서 정당화하십시오. 무언가에 대해 더 빠르다고 말하고, 왜 그런지를 설명하십시오.
이해했습니다
- 직렬: 추가 순서, 추가 빠름, 검색 느림, 로그용 · 순차: 키 필드(key field) 로 정렬됨, 배치 처리 및 순서 출력에 적합 · 랜덤: 레코드 키(record key) 에서 위치 계산됨, 레코드 찾기에 한 번 읽음
- 순차 접근은 시작점에서 읽으며, 직접 접근은 위치로 점프합니다
- 순차 접근은 직렬 및 순차 파일을 지원하며, 직접 접근은 순차 및 랜덤 파일을 지원합니다
- 우선 작업에서 선택하세요: 모든 것을 처리하는가, 하나를 찾는가, 아니면 추가만 하는가