10｜인덱스 구조와 파일 편성

인덱스(Index)는 데이터 레코드의 키와 저장 위치를 연결하여 원하는 레코드에 빠르게 접근하도록 돕는 보조 구조입니다. 파일을 어떤 방식으로 조직하느냐에 따라 순차 처리, 직접 접근, 삽입·삭제의 효율과 필요한 저장공간이 달라집니다.

이 장에서는 B 트리·B+ 트리·트라이 색인의 구조를 살펴보고, 순차 파일·색인 순차 파일(ISAM)·VSAM 파일·직접 파일·역파일의 특징을 비교합니다. 마지막으로 데이터 변화에 따라 인덱스 구조가 고정되는 정적 인덱싱과 함께 변하는 동적 인덱싱의 차이를 정리합니다.

인덱스란 무엇인가?

인덱스는 레코드의 검색 키와 해당 레코드가 저장된 주소 또는 포인터를 대응시킨 구조입니다. 책의 찾아보기에서 용어를 찾은 뒤 페이지 번호로 이동하는 것과 비슷합니다.

구성 요소	의미	예시
검색 키	레코드를 찾기 위한 기준값	학번, 사번, 상품번호
포인터·주소	실제 레코드가 저장된 위치를 가리키는 정보	블록 번호, 페이지 번호, 레코드 주소
색인 항목	검색 키와 포인터를 결합한 항목	사번 103 → 데이터 블록 27
데이터 파일	실제 레코드가 저장된 영역	직원 정보 파일

인덱스를 사용하면 무엇이 달라질까?

B 트리는 어떤 구조일까?

B 트리(B-Tree, Balanced Tree)는 하나의 노드가 여러 키와 여러 자식 포인터를 가질 수 있는 균형 다진 탐색 트리입니다. 모든 리프 노드가 같은 깊이에 위치하므로 데이터가 많아져도 트리의 높이를 낮게 유지할 수 있습니다.

차수가 m인 B 트리를 일반적으로 설명하면 한 노드는 최대 m개의 자식과 최대 m-1개의 키를 가질 수 있습니다. 루트를 제외한 내부 노드는 최소한 일정 수 이상의 자식을 유지하며, 정확한 최솟값은 사용하는 차수 정의에 따라 다르게 표현될 수 있습니다.

항목	내용
키 순서	한 노드 안의 키는 오름차순으로 저장
자식 수	차수 m 기준 최대 m개
키 수	차수 m 기준 최대 m-1개
균형 조건	모든 리프 노드가 같은 깊이에 위치
탐색 시작	루트 노드에서 시작
구조 변경	삽입 시 분할, 삭제 시 재분배·병합 가능

B 트리에서 검색은 어떻게 진행될까?

1. 루트 노드의 키들과 검색 키를 비교합니다.
2. 같은 키가 있으면 해당 노드에서 검색을 마칩니다.
3. 검색 키가 두 키 사이에 있으면 그 구간에 연결된 자식 노드로 이동합니다.
4. 키를 찾거나 더 이동할 자식이 없을 때까지 반복합니다.

B+ 트리는 B 트리와 어떻게 다를까?

B+ 트리는 B 트리를 변형한 다진 균형 탐색 트리입니다. 내부 노드는 검색 경로를 결정하는 키와 포인터를 중심으로 구성하고, 실제 레코드 또는 레코드 포인터는 리프 노드에 저장합니다.

리프 노드들은 일반적으로 키 순서대로 연결되어 있어 하나의 키를 찾은 뒤 다음 키들을 연속해서 읽는 범위 검색과 순차 처리에 유리합니다. 데이터베이스와 파일 시스템의 인덱스에서 널리 사용됩니다.

구분	B 트리	B+ 트리
내부 노드	키와 레코드 위치 정보가 저장될 수 있음	검색 경로용 키와 자식 포인터 중심
리프 노드	키와 레코드 위치 정보 저장 가능	모든 검색 키와 실제 레코드 위치 정보 저장
검색 종료	내부 노드에서도 종료 가능	일반적으로 리프 노드까지 이동
리프 연결	필수 구조가 아님	순차 접근을 위해 연결되는 경우가 일반적
범위 검색	가능하지만 상대적으로 복잡	연결된 리프 노드로 효율적
대표 활용	일반적인 균형 다진 탐색	데이터베이스·파일 시스템 인덱스

트라이 색인은 어떤 방식일까?

트라이(Trie)는 키 전체를 하나의 노드 값으로 저장하기보다 키를 구성하는 문자나 숫자를 경로의 각 단계에 배치하는 트리 구조입니다. 공통 접두사를 가진 키들은 앞부분의 경로를 공유합니다.

예를 들어 CAR, CARD, CAT을 저장하면 첫 문자 C와 다음 문자 A까지는 같은 경로를 사용하고, 이후 R과 T에서 경로가 갈라집니다.

항목	내용
탐색 기준	키를 구성하는 문자·숫자의 순서
탐색 시간	저장 키 수보다 검색 키 길이에 큰 영향을 받음
삽입·삭제	경로의 노드를 추가하거나 정리
장점	접두사 검색과 문자열 키 탐색에 유리
주의점	자식 포인터와 노드 수가 많아지면 공간 사용량 증가

B 트리·B+ 트리·트라이를 한눈에 비교하면?

구분	B 트리	B+ 트리	트라이
핵심 기준	정렬된 키 비교	정렬된 키 비교와 리프 연결	키의 문자·숫자 순서
실제 정보 위치	내부·리프 노드 가능	리프 노드 중심	경로 끝 또는 종료 표시
균형 유지	예	예	필수 조건 아님
범위 검색	가능	매우 효율적	사전식 순회로 가능
접두사 검색	일반적 용도 아님	일반적 용도 아님	효율적
대표 활용	대용량 균형 탐색	DB·파일 시스템 인덱스	사전·자동완성·문자열 검색

파일 편성은 무엇을 결정할까?

파일 편성(File Organization)은 레코드를 저장장치에 어떤 순서와 구조로 기록하고 접근할 것인지를 정하는 방법입니다. 같은 레코드라도 편성 방식에 따라 순차 처리, 임의 접근, 삽입·삭제와 검색의 효율이 달라집니다.

편성 방식	핵심 저장 구조	적합한 처리
순차 파일	논리적 순서대로 연속 저장	전체 자료 일괄 처리
색인 순차 파일	순차 데이터와 별도 색인	순차·직접 접근 병행
VSAM 파일	제어 구간·제어 영역과 동적 색인	순차·직접 접근, 동적 갱신
직접 파일	키에서 물리 주소 계산	빠른 랜덤 접근
역파일	항목값에서 레코드 위치 목록으로 연결	조건 검색·문서 검색

순차 파일은 어떻게 구성될까?

순차 파일(Sequential File)은 레코드를 논리적 순서에 따라 차례로 저장하고, 일반적으로 앞에서부터 순차적으로 접근하는 방식입니다. 일반적으로 첫 레코드부터 차례대로 읽으므로 전체 자료를 처리하는 일괄 작업에 적합합니다.

장점	단점
구조가 단순하고 연속 읽기 속도가 빠름	특정 레코드 하나를 찾으려면 앞부분부터 검색해야 할 수 있음
레코드 사이의 빈 공간이 적어 저장장치를 효율적으로 사용	중간 위치의 삽입·삭제가 어렵고 파일 재작성 비용이 발생
자기테이프와 디스크 등 다양한 입출력 매체에 적용 가능	대화식 랜덤 처리보다 일괄 처리에 적합

색인 순차 파일(ISAM)은 무엇일까?

색인 순차 파일(ISAM: Indexed Sequential Access Method)은 키 순서대로 저장된 데이터 영역과 해당 데이터 위치를 찾기 위한 별도의 색인 영역을 함께 사용하는 파일 구조입니다. 순차 접근과 직접 접근을 모두 지원하도록 설계되었습니다.

레코드를 직접 찾을 때는 상위 색인부터 하위 색인으로 탐색한 뒤, 색인이 가리키는 데이터 블록이나 트랙으로 이동합니다. 새 레코드를 삽입할 때 기본 영역의 적절한 위치에 공간이 없으면 오버플로 영역을 사용합니다.

ISAM의 주요 영역

영역	역할
기본 영역	키 순서에 따라 데이터 레코드를 저장
트랙 색인	트랙 단위의 데이터 위치를 가리킴
실린더 색인	실린더 안에서 필요한 트랙 색인으로 연결
마스터 색인	상위 단계에서 실린더 색인을 가리킴
실린더 오버플로 영역	해당 실린더의 기본 영역에 삽입할 공간이 부족할 때 사용
독립 오버플로 영역	실린더 오버플로 공간까지 부족할 때 별도 위치에 저장

ISAM의 장단점

VSAM 파일은 ISAM과 어떻게 다를까?

이 글의 VSAM 색인 구조와 동적 분할 설명은 시험에서 주로 다루는 키 순서 데이터 세트(KSDS)를 중심으로 합니다.

VSAM(Virtual Storage Access Method)은 직접 접근 저장장치에서 레코드를 효율적으로 관리하기 위한 접근 방식입니다. 키 순서 데이터 세트에서는 레코드를 키 순서로 저장하고 색인을 통해 순차 접근과 직접 접근을 지원합니다.

VSAM은 데이터를 제어 구간(Control Interval)에 저장하고, 여러 제어 구간을 제어 영역(Control Area)으로 묶어 관리합니다. 키 순서 데이터 세트의 색인은 하위의 시퀀스 세트(Sequence Set)와 그 위의 인덱스 세트(Index Set)로 구성될 수 있습니다.

구성 요소	의미
제어 구간(CI)	레코드가 실제로 저장되는 기본 입출력 단위
제어 영역(CA)	연속된 여러 제어 구간을 묶은 상위 저장 단위
시퀀스 세트	데이터 제어 구간을 직접 가리키는 최하위 색인 수준
인덱스 세트	시퀀스 세트의 상위 수준 색인
빈 공간	향후 삽입을 위해 제어 구간·제어 영역에 미리 남겨 둘 수 있는 공간

VSAM의 특징

• 순차 접근과 직접 접근을 모두 지원할 수 있습니다.
• ISAM처럼 기본 영역과 고정된 별도 오버플로 영역을 엄격히 나누기보다 제어 구간과 제어 영역의 빈 공간을 활용합니다.
• 삭제된 레코드의 공간을 다시 사용할 수 있습니다.
• 제어 구간에 공간이 부족하면 제어 구간 분할이, 제어 영역까지 부족하면 제어 영역 분할이 발생할 수 있습니다.
• 색인과 데이터 구조가 삽입·삭제에 따라 동적으로 조정됩니다.

ISAM과 VSAM을 비교하면?

구분	ISAM	VSAM
기본 구조	기본 영역·색인 영역·오버플로 영역	제어 구간·제어 영역·동적 색인
삽입 처리	기본 영역이 차면 오버플로 영역 사용	빈 공간 활용 후 필요하면 CI·CA 분할
삭제 공간 재사용	제한적이고 재편성이 필요할 수 있음	재사용 가능
색인 변화	상대적으로 정적	데이터 변화에 따라 동적
성능 저하 원인	오버플로 체인 증가	빈번한 분할과 비효율적 공간 배치
대표 성격	전통적인 색인 순차 편성	동적 색인 순차 접근 방식

직접 파일은 어떻게 접근할까?

직접 파일(Direct File)은 레코드 키에 해시 함수와 같은 주소 변환 함수를 적용하여 레코드가 저장될 물리적 위치를 계산하는 방식입니다. 앞의 레코드를 차례대로 읽지 않고 원하는 위치에 직접 접근합니다.

항목	내용
접근 원리	레코드 키에서 저장 주소 계산
대표 기술	해싱
처리 방식	랜덤·대화식 처리에 적합
장점	특정 레코드에 빠르게 접근
단점	주소 충돌 처리와 여유 공간이 필요해 저장공간 효율이 낮아질 수 있음

역파일은 무엇을 뒤집은 구조일까?

역파일(Inverted File)은 레코드에서 속성값을 찾는 일반적인 방향과 반대로, 검색 항목이나 속성값에서 해당 값을 가진 레코드들의 위치 목록으로 연결하는 구조입니다.

예를 들어 문서 파일에서 각 단어를 색인 키로 만들고, 그 단어가 포함된 문서 번호들의 목록을 저장할 수 있습니다. ‘인덱스’라는 단어를 검색하면 해당 단어가 등장한 문서들의 위치를 바로 확인할 수 있습니다.

검색 항목	레코드 위치 목록
인덱스	문서 1, 문서 4, 문서 8
파일	문서 2, 문서 4, 문서 7
트리	문서 1, 문서 3

파일 편성 방법을 한눈에 비교하면?

구분	순차 파일	ISAM	VSAM	직접 파일	역파일
저장 기준	논리적 순서	키 순서+색인	CI·CA와 색인	계산된 주소	항목별 위치 목록
순차 접근	우수	가능	가능	주목적 아님	주목적 아님
직접 접근	비효율적	가능	가능	우수	검색 항목 기준 우수
삽입·삭제	재작성 비용 큼	오버플로 발생	동적 분할·공간 재사용	충돌 처리 필요	역색인 갱신 필요
추가 공간	적음	색인·오버플로 필요	색인·빈 공간 필요	여유 슬롯 필요	색인 목록 필요
대표 용도	일괄 처리	순차·직접 병행	동적 대용량 파일	랜덤 조회	문서·조건 검색

정적 인덱싱과 동적 인덱싱은 어떻게 다를까?

정적 인덱싱(Static Indexing)은 레코드가 삽입·삭제되어도 색인의 전체 구조가 자동으로 균형 있게 재구성되지 않는 방식입니다. 데이터 영역과 색인 영역을 별도 파일로 구성하고, 삽입이 누적되면 오버플로 영역이나 주기적인 재편성에 의존할 수 있습니다.

동적 인덱싱(Dynamic Indexing)은 레코드 삽입·삭제에 맞춰 노드를 분할·병합하거나 색인 구조를 재조정합니다. B 트리와 B+ 트리가 대표적이며, 데이터 변화가 잦아도 검색 효율을 일정하게 유지하도록 설계됩니다.

구분	정적 인덱싱	동적 인덱싱
색인 구조 변화	자동 구조 조정이 제한적	삽입·삭제에 따라 분할·병합
데이터 증가 처리	오버플로 영역 사용	노드 분할로 공간 확보
성능 유지	오버플로 누적 시 저하	균형 구조를 유지해 비교적 안정적
재편성	주기적으로 필요할 수 있음	구조가 자동 조정되어 필요성이 낮음
대표 예	전통적 ISAM	B 트리·B+ 트리 기반 색인

시험에서 자주 혼동되는 개념

이번 장 핵심 요약

1. 인덱스는 검색 키와 레코드 주소를 연결하여 검색 속도를 높입니다.
2. B 트리는 여러 키와 자식을 가진 균형 다진 탐색 트리입니다.
3. B+ 트리는 실제 레코드 위치 정보를 리프 노드에 모으고 리프를 연결합니다.
4. 트라이는 키의 문자나 숫자 순서를 경로로 표현합니다.
5. 순차 파일은 연속 처리와 일괄 작업에 적합하지만 직접 검색과 삽입이 비효율적입니다.
6. ISAM은 기본 영역·색인 영역·오버플로 영역으로 구성됩니다.
7. ISAM의 물리적 색인은 트랙·실린더·마스터 색인으로 구성됩니다.
8. VSAM은 제어 구간과 제어 영역을 사용하며 삽입 시 분할이 발생할 수 있습니다.
9. 직접 파일은 해시 함수 등으로 저장 주소를 계산합니다.
10. 역파일은 검색 항목별로 해당 레코드의 위치 목록을 저장합니다.
11. 정적 인덱싱은 오버플로 누적 시 재편성이 필요할 수 있습니다.
12. 동적 인덱싱은 삽입·삭제에 따라 노드를 분할·병합하여 구조를 유지합니다.

복습 문제

인덱스의 기본 역할은 무엇인가?

검색 키와 레코드의 저장 위치를 연결하여 원하는 레코드에 빠르게 접근하도록 돕는 것입니다.

B 트리의 모든 리프 노드는 어떤 특징을 가질까?

모든 리프 노드는 같은 깊이에 위치합니다.

B+ 트리에서 실제 레코드 위치 정보는 주로 어디에 저장될까?

리프 노드에 저장됩니다.

키를 구성하는 문자나 숫자의 순서를 경로로 표현하는 구조는?

트라이(Trie)입니다.

대량의 레코드를 처음부터 순서대로 처리하는 데 적합한 파일은?

순차 파일입니다.

해시 함수로 레코드 키를 물리 주소로 변환하는 파일 편성은?

직접 파일입니다.

ISAM의 물리적 색인 세 가지는?

트랙 색인, 실린더 색인, 마스터 색인입니다.

ISAM의 색인 구성에 해당하지 않는 것은: 트랙·실린더·마스터·볼륨 색인?

볼륨 색인입니다.

ISAM에서 삽입이 누적되면 검색 성능이 낮아지는 주된 이유는?

오버플로 영역과 오버플로 체인이 증가하기 때문입니다.

VSAM에서 레코드가 저장되는 기본 입출력 단위는?

제어 구간(Control Interval)입니다.

여러 제어 구간을 묶은 VSAM의 상위 저장 단위는?

제어 영역(Control Area)입니다.

검색 항목에서 그 항목을 가진 레코드 위치 목록으로 연결하는 구조는?

역파일 또는 역색인 구조입니다.

데이터 삽입·삭제에 따라 노드가 분할·병합되는 인덱싱은?

동적 인덱싱입니다.