3.1.4. 인덱스와 해싱 활용: 인덱스 원리, 해시 함수 및 해싱 활용

인덱스의 종류와 해싱의 충돌(Collision) 해결 기법이 단골 주제로 출제됩니다.

1. 인덱스 (Index)의 원리

인덱스는 데이터 레코드를 빠르게 찾기 위해 <키 값, 포인터> 쌍으로 구성된 데이터 구조입니다. 책의 맨 뒤에 있는 '찾아보기(색인)'와 정확히 같은 역할을 합니다.

• 기본 원리: 레코드가 저장된 물리적 주소를 별도의 파일로 관리하여 검색 시 전체 데이터를 다 뒤지지(Full Scan) 않게 합니다.
• 장점: 검색 속도가 향상되고 시스템의 전체적인 성능이 좋아집니다.
• 단점: 인덱스를 저장하기 위한 추가 공간이 필요하며, 데이터 삽입/삭제/수정이 빈번할 경우 인덱스를 계속 갱신해야 하므로 오히려 성능이 떨어질 수 있습니다.

인덱스의 종류 (시험 단골)

1. 클러스터드 인덱스 (Clustered Index):
   • 실제 데이터 저장 순서와 인덱스 설정 순서가 같습니다.
   • 영어 사전처럼 내용 자체가 정렬되어 있습니다.
   • 테이블당 하나만 만들 수 있으며, 검색 속도가 매우 빠릅니다.
2. 넌클러스터드 인덱스 (Non-Clustered Index):
   • 인덱스 파일과 실제 데이터 파일이 분리되어 있습니다.
   • 일반 책의 '색인' 페이지와 같습니다.
   • 여러 개를 만들 수 있지만, 클러스터드보다 검색 속도는 느립니다.

---

2. 해싱 (Hashing)의 이해

해싱은 키 값을 **해시 함수(Hash Function)**라는 산술식에 대입하여 나온 결과값(해시 주소)을 통해 데이터의 위치를 바로 찾아가는 방식입니다.

• 특징: 검색 속도가 **$O(1)$**로 모든 탐색 알고리즘 중 가장 빠릅니다.
• 주요 용어:
  • 버킷(Bucket): 하나의 주소에 할당된 저장 공간.
  • 슬롯(Slot): 버킷 안에서 한 개의 레코드를 저장할 수 있는 공간.
  • 충돌(Collision): 서로 다른 키가 같은 해시 주소(버킷)로 배정되는 현상.
  • 오버플로(Overflow): 버킷의 슬롯이 가득 차서 더 이상 저장할 수 없는 상태.
  • 시노님(Synonym): 같은 버킷 주소를 가지는 키들의 집합.

---

3. 해시 함수 및 충돌 해결 기법

가. 대표적인 해시 함수

• 제산법 (Division): 키 값을 큰 소수(Prime Number)로 나눈 나머지를 주소로 결정합니다.
• 폴딩법 (Folding): 키 값을 여러 부분으로 나누고, 이를 더하거나 XOR 연산하여 주소를 만듭니다.
• 중간 제곱법 (Mid-Square): 키 값을 제곱한 뒤 중간의 일부 자릿수를 주소로 사용합니다.
• 숫자 분석법 (Digit Analysis): 키 값의 각 자릿수 분포를 분석하여 가장 고른 분포를 가진 자리를 선택합니다.

나. 충돌 해결 방법 (★매우 중요)

1. 개방 주소법 (Open Addressing): 충돌이 나면 주변의 다른 빈 버킷을 찾아 들어가는 방식입니다. (예: 선형 조사법)
2. 체이닝 (Chaining): 충돌이 발생한 주소에 데이터를 **연결 리스트(Linked List)**로 매달아 관리하는 방식입니다.
3. 재해싱 (Re-hashing): 충돌 시 새로운 해시 함수를 한 번 더 적용합니다.

---

필기 시험 핵심 요약

1. 인덱스의 단점: "데이터의 삽입/삭제가 빈번할 때는 성능이 저하될 수 있다"는 지문을 주의 깊게 보세요.
2. 해싱 주소 계산: 제산법($MOD$ 연산) 문제가 계산식으로 나올 수 있습니다.
3. 해싱 현상: 충돌(Collision)이 발생한다고 해서 항상 오버플로가 일어나는 것은 아닙니다. (버킷에 슬롯이 여러 개 있을 수 있기 때문)
4. 속도 순서: 해싱($O(1)$) > 이진 탐색($O(\log n)$) > 순차 탐색($O(n)$) 순으로 빠릅니다.