데이터베이스 파일 구조 - 순차, 인덱스, 해싱 접근 방식
선수학습(1개)
요약
데이터베이스 파일 구조의 핵심인 순차 접근, 인덱스 순차 접근, 해싱 접근 방식에 대해 알아보고 각 방식의 장단점과 사용 사례를 비교 분석합니다.
| 구분 | 순차 접근 | 인덱스 접근 | 해싱 접근 |
|---|---|---|---|
| 주요 접근 방식 | 순차 | 순차 + 임의 | 임의 |
| 검색 속도 | 느림 | 보통 ~ 빠름 | 매우 빠름 |
| 데이터 변경 | 비효율적 | 오버헤드 발생 | 효율적 (충돌 시 성능 저하) |
| 저장 공간 | 효율적 | 추가 공간 필요 | 낭비 가능성 있음 |
| 적합한 업무 | 배치 처리 | 순차/임의 처리 혼합 | 실시간 조회 |
데이터베이스가 디스크에 데이터를 저장하고 검색하는 방식, 즉 파일 구조는 데이터베이스 시스템 전체 성능에 지대한 영향을 미칩니다. 사용자가 원하는 데이터를 얼마나 빠르고 효율적으로 찾을 수 있는지는 파일 구조에 따라 결정됩니다.
순차 접근 (Sequential Access)
순차 접근은 가장 간단한 파일 구조입니다. 이름에서 알 수 있듯이, 레코드가 파일에 저장된 순서대로 차례차례 접근하는 방식입니다. 마치 카세트테이프에서 원하는 노래를 찾기 위해 처음부터 순서대로 들어보는 것과 같습니다.
- 저장 방식: 레코드는 보통 입력된 순서나 특정 필드(예: 학번, 입사일)를 기준으로 정렬되어 물리적으로 연속된 공간에 저장됩니다.
- 탐색 방식: 특정 레코드를 찾으려면 파일의 처음부터 끝까지 순차적으로 모든 레코드를 읽어 비교해야 합니다.
순차 접근의 장점
- 단순성: 구조가 매우 간단하고 구현하기 쉽습니다.
- 순차 처리 효율성: 전체 데이터를 순차적으로 처리하는 작업(예: 전체 직원의 급여 총합 계산)에 매우 효율적입니다.
- 저장 공간 효율성: 레코드를 연속적으로 저장하므로 추가적인 공간(예: 인덱스)이 필요 없어 저장 공간을 효율적으로 사용할 수 있습니다.
순차 접근의 단점
- 느린 검색 속도: 특정 레코드를 직접 찾아야 하는 '임의 접근(Random Access)'의 경우, 평균적으로 파일의 절반을 읽어야 하므로 매우 비효율적입니다. 파일이 클수록 검색 시간은 급격히 늘어납니다.
- 수정 및 삭제의 어려움: 중간에 레코드를 삽입하거나 삭제하려면 해당 위치 이후의 모든 레코드를 이동시켜야 하는 큰 오버헤드가 발생합니다.
사용 사례
- 배치 처리(Batch Processing): 급여 일괄 처리, 월말 결산 등과 같이 전체 데이터를 순차적으로 읽어 처리하는 작업에 적합합니다.
- 로그 파일: 시간 순서대로 발생하는 이벤트를 기록하고 분석할 때 유용합니다.
인덱스(색인) 접근 (Indexed Access)
순차 접근의 느린 검색 속도를 해결하기 위해 인덱스(Index, 색인) 를 사용하는 방식입니다. 책의 맨 뒤에 있는 '찾아보기' 페이지처럼, 데이터 자체와는 별도로 키 값과 해당 데이터의 위치(주소)를 담은 인덱스 테이블을 만들어 사용합니다. 특정 데이터를 찾을 때, 전체 데이터를 뒤지는 대신 크기가 작은 인덱스 테이블을 먼저 탐색하여 원하는 데이터의 위치를 빠르게 알아낼 수 있습니다.
- 탐색 방식:
- 먼저 인덱스 파일에서 찾고자 하는 키 값을 탐색합니다.
- 인덱스에서 해당 키 값에 연결된 포인터(주소)를 얻습니다.
- 포인터를 이용해 데이터 파일에서 원하는 레코드가 저장된 위치로 직접 접근합니다.
인덱스를 구현하는 방식은 다양하며, 대표적인 예가 바로 아래에서 설명할 인덱스 순차 접근 방식(ISAM) 과 현대 데이터베이스에서 널리 쓰이는 B-트리(B-Tree) 입니다.
인덱스 순차 접근 방식 (ISAM) 요약
ISAM(Indexed Sequential Access Method)은 인덱스를 통해 빠른 임의 접근과 순차 접근을 모두 지원하는 초기 파일 구조입니다. 데이터는 기본 키 순서로 정렬되어 있고, 별도의 인덱스 파일을 통해 특정 데이터의 위치를 빠르게 찾을 수 있습니다. 하지만 데이터 추가 및 삭제 시 구조 변경이 비효율적이고 주기적인 재구성이 필요한 단점이 있어, 현재는 B-트리에 밀려 잘 사용되지 않습니다.
B-트리 (B-Tree) 요약
B-트리는 현대 데이터베이스 시스템에서 가장 널리 사용되는 인덱스 자료구조입니다. ISAM의 단점을 개선하여 데이터 추가/삭제 시 발생하는 오버헤드를 최소화하고, 스스로 균형을 맞추는(self-balancing) 특징이 있습니다. 이를 통해 어떤 키 값으로 검색하더라도 항상 일정한 속도를 보장합니다. 대용량 데이터 저장 및 검색에 매우 효율적입니다.
해싱 접근 (Hashing)
해싱 접근은 키 값을 해시 함수(Hash Function) 에 입력하여 나온 결과값(해시 주소)을 레코드의 물리적 주소로 사용하는 매우 빠른 임의 접근 방식입니다. 키 값만 알면 계산을 통해 즉시 레코드가 저장된 위치를 알 수 있어, 검색 과정이 거의 필요 없습니다.
-
저장 방식:
- 레코드의 키 값을 해시 함수에 적용합니다.
- 해시 함수는 특정 계산을 통해 고정된 길이의 해시 주소(버킷 주소)를 반환합니다.
- 이 해시 주소를 레코드가 저장될 디스크 상의 위치로 사용합니다.
-
해시 충돌 (Hash Collision): 서로 다른 키 값이 해시 함수를 통해 동일한 해시 주소를 반환하는 경우를 해시 충돌이라고 합니다. 이는 해싱 접근 방식에서 반드시 해결해야 하는 문제입니다.
- 해결 방안:
- 체이닝(Chaining): 동일한 해시 주소를 갖는 레코드들을 연결 리스트(Linked List)로 묶어 관리합니다.
- 개방 주소법(Open Addressing): 충돌이 발생하면 미리 정해진 규칙에 따라 다른 빈 공간을 찾아 데이터를 저장합니다.
- 해결 방안:
해싱 접근의 장점
- 매우 빠른 임의 접근 속도: 키 값을 통해 레코드의 위치를 직접 계산하므로, 파일 크기와 상관없이 거의 즉각적인 검색이 가능합니다. 평균적인 탐색 복잡도는 O(1)에 가깝습니다.
해싱 접근의 단점
- 순차 접근의 어려움: 데이터가 키 값의 해시 결과에 따라 흩어져 저장되므로, 순차적인 접근이 매우 비효율적입니다.
- 해시 함수 의존성: 좋은 해시 함수를 설계하는 것이 중요합니다. 해시 함수가 충돌을 얼마나 잘 피하고 데이터를 고르게 분산시키느냐에 따라 전체 성능이 좌우됩니다.
- 저장 공간 낭비: 해시 충돌을 줄이기 위해 실제 데이터 양보다 더 많은 저장 공간(버킷)을 할당해야 할 수 있어 공간 낭비가 발생할 수 있습니다.
사용 사례
- 빠른 조회가 필수적인 온라인 트랜잭션 처리(OLTP) 시스템이나 데이터베이스 내부의 인덱싱 구조(해시 인덱스) 등에서 활용됩니다.
어떤 방식을 선택해야 할까?
세 가지 파일 구조는 각각의 장단점이 명확하므로, 어떤 방식을 선택할지는 애플리케이션의 요구사항에 따라 달라집니다.
- 전체 데이터를 순차적으로 처리하는 작업이 대부분이라면 순차 접근이 좋은 선택입니다.
- 순차 처리와 임의 조회가 모두 필요하다면 인덱스 순차 접근이 가장 유연한 해결책이 될 수 있습니다.
- 무엇보다 빠른 임의 접근 속도가 중요하다면 해싱 접근이 가장 강력한 성능을 보여줄 것입니다.