Chap 6-2

개념	간단 설명	장점	단점
Sequential Search	순차적으로 처음부터 끝까지 키를 찾음	단순하고 구현이 쉬움	O(n) 비교, 대용량 파일에 비효율적
Binary Search	정렬된 파일에서 중간부터 이진 탐색	O(log n)의 빠른 검색	파일이 정렬되어 있어야 하며, 삽입·삭제 시 재정렬 비용 큼
Internal Sort	메모리에 데이터를 모두 올려 정렬 (예: UNIX sort)	빠르고 효율적인 정렬 가능	큰 파일엔 불가능, 메모리 용량 제한
Key Sorting	키만 메모리에 올려 정렬하고 해당 RRN(레코드 번호) 기반으로 원본 정렬	RAM 사용량 절감, 효율적 키 정렬	기록 재읽기/재쓰기 → I/O 비용 증가, seek cost 큼

Chap 7

개념	간단 설명	장점	단점 및 문제점/해결방안
Index	키-주소 쌍으로 구성된 별도 파일, 빠른 검색 지원	검색 성능 향상, 정렬 불필요, 고정길이레코드 사용 시 삽입 삭제 쉬움, 데이터 파일보다 훨씬 작음	대규모 인덱스는 메모리 부족 가능 → 해시 구조 또는 B-tree 사용 권장
Index가 너무 클 때	디스크에 저장된 인덱스를 다루는 경우	–	Binary search시에 디스크 seek 비용 큼, 재정렬 시 비용 큼 → 트리 구조(B-tree), 해시 인덱스 활용
Secondary Key	주 키 외의 보조 검색 키 (예: 작곡가)	다양한 검색 조건 지원	데이터 중복, 삭제/수정 시 모든 인덱스 갱신 필요 → 배열/리스트 방식으로 구조 개선
Secondary Key - Array 방식	하나의 보조 키에 여러 주 키를 배열로 저장	접근 속도 빠름	고정 크기 한계, 공간 낭비 (internal fragmentation)
Secondary Key - List 방식	보조 키마다 연결 리스트로 주 키 저장	정적 길이, 삭제 후 공간 재활용 용이	locality 떨어져 seek 비용 증가, 데이터가 물리적으로 인접하지 않음

➤ Primary Key로 매핑해야 하는 경우

데이터를 자주 정렬, 재구성, 재배치하는 경우
파일 내 레코드가 이동 가능성이 있는 경우
재사용 가능한 인덱스 구조를 원할 때 (ex. indexing layer 유지)
복합 인덱스나 조합 질의를 많이 수행할 때

→ ✅ 대부분의 DBMS는 이 방식을 사용

→ secondary → primary key → primary index → byte offset → 레코드

➤ Byte Offset으로 매핑하는 것이 나은 경우

파일이 **불변(append-only)**이거나
모든 데이터가 **정적(static)**인 경우
접근 속도가 중요한 단순한 단일 질의만 존재할 때

→ 예: 단순 검색 전용 로그 파일, 아카이브 등

Chap 8

개념	간단 설명	장점	단점
Match	두 정렬 리스트에서 공통 항목 추출	교집합 추출 용이, 효율적 처리	리스트 정렬 필요, 중복 키 불허 가정
Merge	두 정렬 리스트를 하나로 병합	합집합 생성, 정렬 유지	두 리스트 모두 끝까지 읽어야 함
K-way Merge	K개의 정렬 리스트를 병합	여러 리스트 병합 가능	비교 횟수 많음 → selection tree로 개선
Selection Tree	K-way 병합 시 최소값을 빠르게 선택하는 트리 구조	O(log K) 비교로 효율적 병합	구현 복잡도 있음
Heap Sort	heap 구조를 이용한 메모리 내 정렬	정렬 성능 좋음, 메모리 적절히 활용	삽입/삭제에 시간 소요
Merge Sort (External)	외부 저장장치 사용, run 생성 후 병합	대용량 정렬 가능, 효율적인 디스크 접근	seek 비용 많음 → RAM 확장, 병렬 디스크, I/O 채널 활용으로 개선 가능

Chap 9