파일 조직은 파일 안 레코드를 어떤 순서와 구조로 놓을지다. 들어온 순서대로 쌓기만 하면 넣기는 쉽지만 찾을 때 처음부터 끝까지 뒤져야 하고, 키 순서로 정렬해 두면 차례로 읽기는 좋지만 하나를 찾거나 끼워 넣기는 어렵다. 색인이나 해시를 더하면 찾기가 빨라지는 대신 공간과 갱신 비용이 든다. 읽기 전용 CD냐 자주 고치는 하드 디스크냐처럼 쓰임새에 따라 답이 다르다.
예시로 보기
학번으로 학생 한 명을 찾는다고 하자1.
| 조직 | 찾는 법 | 레코드 \(n\)개일 때 |
|---|---|---|
| 더미 | 처음부터 끝까지 비교 | 평균 \(n/2\)번 |
| 순차 | 키 순서로 정렬되어 있지만 테이프처럼 차례로 읽는다면 여전히 앞에서부터 | 평균 \(n/2\)번 |
| 색인 순차 | 색인에서 근처 위치를 찾고, 그 위치부터 차례로 | 색인 한 단계면 약 \(\sqrt{n}\) 수준 |
| 색인 | 학번 색인에서 바로 위치를 찾음 | 색인 검색 + 1번 |
| 해시 | 학번을 해시 함수에 넣어 블록 주소를 바로 계산 | 거의 1번 |
정확히 말하면
파일 조직은 레코드의 논리적 구조이고, 파일에 어떻게 접근하느냐에 따라 정한다. 기준은 짧은 접근 시간, 쉬운 갱신, 저장 공간 절약, 간단한 유지, 신뢰성이다. 우선순위는 쓰임에 따라 다르고(읽기 전용 CD와 하드 디스크), 서로 부딪히기도 한다.
| 조직 | 구조 | 특징 |
|---|---|---|
| 더미 (pile) | 들어온 순서대로 쌓는다. 구조가 없다. 레코드마다 필드가 다를 수 있다 | 많은 데이터를 모아 저장하는 것이 목적. 찾으려면 전부 뒤져야 한다 |
| 순차 | 레코드 형식이 고정이다. 길이가 같고 필드의 순서와 길이가 같다. 필드 이름과 길이는 파일의 속성이다. 레코드를 유일하게 가리키는 키 필드 순으로 저장한다 | 모든 레코드를 차례로 처리하는 일괄 작업에 좋다. 하나를 찾거나 끼워 넣기는 어렵다 |
| 색인 순차 | 키 순으로 정렬하는 순차 파일의 성질을 지키면서, 아무 데나 바로 가기 위한 색인과 오버플로 파일을 더한다 | 새 레코드는 오버플로 파일에 넣고 주 파일의 앞 레코드에서 포인터로 잇는다 |
| 색인 | 키 필드마다 색인을 따로 여러 개 둔다. 모든 레코드의 항목을 가진 완전 색인이나, 일부만 가진 부분 색인 | 새 레코드를 넣으면 모든 색인을 고쳐야 한다 |
| 직접(해시) | 주소를 아는 블록에 바로 간다. 레코드마다 키 필드가 필요하다 | 키를 해시해 블록 주소를 계산한다 |
색인 (키 일부만) 주 파일 (키 순서) 오버플로 파일
+--------+ +-----+--------+ +-----+--------+
| 키 10 | --------> | 10 | 레코드 |
| | | 20 | 레코드 | ------>| 25 | 레코드 |
| 키 40 | ----+ | 30 | 레코드 | +-----+--------+
+--------+ +---->| 40 | 레코드 |
| 50 | 레코드 |
+-----+--------+
색인 순차 파일에서 키 25짜리 레코드를 나중에 넣은 모습이다. 색인은 근처 위치(키 10이나 40)로 바로 데려다 주고, 그다음은 주 파일을 차례로 읽는다. 끼워 넣은 25는 주 파일을 다시 정렬하지 않고 오버플로 파일에 두며, 바로 앞 레코드 20이 포인터로 가리킨다2.
성능 비교
A(매우 좋음)부터 F(맞지 않음)까지의 등급이다. \(r\)은 결과 크기, \(o\)는 넘친 레코드 수, \(n\)은 파일의 레코드 수다3.
| 조직 | 공간: 가변 속성 | 공간: 고정 속성 | 갱신: 같은 크기 | 갱신: 더 큰 크기 | 검색: 레코드 하나 | 검색: 일부 | 검색: 전부 |
|---|---|---|---|---|---|---|---|
| 더미 | A | B | A | E | E | D | B |
| 순차 | F | A | D | F | F | D | A |
| 색인 순차 | F | B | B | D | B | D | B |
| 색인 | B | C | C | C | A | B | D |
| 해시 | F | B | B | F | B | F | E |
| 등급 | 뜻 | 대략의 비용 |
|---|---|---|
| A | 매우 좋음 | \(O(r)\) |
| B | 좋음 | \(O(o \times r)\) |
| C | 적당 | \(O(r \log n)\) |
| D | 추가 노력 필요 | \(O(n)\) |
| E | 아주 큰 노력으로 가능 | \(O(r \times n)\) |
| F | 이 목적에 맞지 않음 | \(O(n^{>1})\) |
표를 읽는 예: 해시 파일은 레코드 하나 찾기는 B(좋음)지만, “일부” 검색(예: 학번 2020~2022 범위)은 F다. 해시가 키 순서를 흩어 놓기 때문이다.
활용
- 데이터베이스의 B+트리 색인은 색인 순차 파일을 발전시킨 것이고, 해시 색인은 직접 파일과 같은 생각이다1.
- 로그 파일은 더미처럼 끝에 계속 붙인다. 넣기가 가장 싸고, 읽을 때는 대개 전부 훑는다1.
연결
- 선수: 파일과 파일 관리 시스템
- 레코드를 블록에 담는 방법: 레코드 블로킹
- 해시와 이진 탐색: 2-1학기 알고리즘
과목별 관점
데이터베이스 설계 (2-2학기). 위 표의 “색인”을 실제로 어떤 모양으로 만드는지를 다룬다. 실제 데이터베이스는 주기억장치에 다 올라가지 않아 디스크에 두고, 필요한 조각만 읽어 와 고친 뒤 다시 쓴다. 디스크는 주기억장치보다 훨씬 느리므로 색인의 좋고 나쁨을 “찾는 데 디스크를 몇 번 읽는가”로 잰다.
색인을 이진 탐색 트리로 만들면 노드 하나에 키가 하나뿐이라, 균형이 잡혀 있어도 노드를 여럿 읽어야 한다. 노드 하나에 키를 여러 개 담고 모든 잎의 깊이를 같게 맞춘 균형 탐색 트리가 B-트리다. 한 예에서 같은 키를 찾는 데 레드-블랙 트리는 디스크를 5번, B-트리는 2번 읽는다. 많은 데이터베이스 시스템이 B-트리나 그 변형(B+-트리, B*-트리)을 쓴다.
B-트리의 노드 하나는 디스크 페이지 하나에 담는다. 그래서 노드를 하나 내려갈 때마다 디스크를 한 번 읽고, 검색 한 번에 읽는 횟수는 트리의 높이에 비례한다. 찾아 내려가는 절차는 B-트리 검색에 있다.
확인 문제
C1 다음 쓰임에 가장 맞는 파일 조직은? ① 월말에 전 직원 급여를 한꺼번에 계산 ② 주민번호로 한 사람을 즉시 조회, 범위 검색은 없음 ③ 센서 측정값을 들어오는 대로 저장만 해 둠
답: ① 순차(전부 차례로 처리, 성능 비교 표의 “전부” A) ② 해시(레코드 하나 B, 범위 검색 불필요) ③ 더미(넣기가 가장 쉬움, 공간 A).
C2 순차 파일에 레코드를 끼워 넣기가 어려운 이유와, 색인 순차 파일이 이를 어떻게 피하는지 쓰라.
답: 키 순서를 지켜야 하므로, 중간에 넣으려면 뒤의 레코드를 모두 밀어야 한다. 색인 순차 파일은 새 레코드를 오버플로 파일에 넣고 주 파일의 앞 레코드에서 포인터로 이어, 주 파일을 다시 쓰지 않는다. 오버플로가 쌓이면 주기적으로 합쳐 정리한다.
C3 성능 비교 표에서 색인 파일의 “검색: 레코드 하나 A, 검색: 전부 D”를 말로 풀어 쓰라.
답: 색인이 있어 레코드 하나는 결과 크기 정도의 비용(\(O(r)\))으로 바로 찾는다. 하지만 모든 레코드를 읽으려면 색인을 따라 흩어진 레코드를 하나씩 찾아야 해서 파일 크기에 비례하는 추가 노력(\(O(n)\))이 든다.