[정보처리기사 필기 요약] 인덱스(INDEX) (2)

* 해시 인덱스

• 데이터 신속한 검색 위해 키 값에 해시 함수 적용하여 주소 값 빠르게 계산하고 레코드 저장된 위치 직접 접근하는 방법
• (키 값, 주소) 쌍으로 저장하므로 특정 키 값에 대한 검색 방법 중 가장 빠름

구분	설명
버킷(Bucket)	- 동일한 해시 주소 갖는 레코드(키와 주소쌍)들이 저장될 메모리 블록 의미. - 버킷 크기에 따라 같은 해시 주소에 저장될 수 있는 레코드 수 결정
슬롯(Slot)	- 1개의 해시 레코드 저장할 수 있는 공간 의미. n개의 슬롯이 모여 하나의 버킷을 이룸
충돌(Collision)	- 해시 레코드 삽입 시 서로 다른 2개 이상의 데이터가 같은 해시 주소 갖는 현상
동거자(Synonyms)	- 해시 함수가 같은 주소로 변환시키는 모든 레코드
오버플로우(Overflow)	- 계산된 해시 주소 버킷 내 저장할 공간 없는 상태를 오버플로우가 발생했다 라고 하며 별도 오버플로우 처리 방법 필요 - 해시 버킷이 꽉 찬 상태에서 다른 레코드가 해당 버킷에 추가되는 경우

 

• 해시 함수 종류

구분	설명
계수 분석 (Digit Analysis)	- 키 값 구성하는 숫자 분포 파악하여 분포가 비교적 고른 자리부터 필요한 자리만큼 선택하여 레코드 주소 결정
제산법 (Division)	- 키를 임의의 양의 정수로 나눈 나머지를 그 키의 레코드 저장하는 주소로 결정 - 키 K, 양의 정수 n이라 할 때 해시 함수는 h(k) = K mod n, 이때 0 <= h(k) < n 만족
제곱법 (Mid-sqare)	- 키 값 제곱한 값의 중간 부분 값을 선택하여 레코드 주소로 결정 - 예: h(265)는 70225의 중간 값 022
폴딩 (Folding)	- 키를 여러 부분으로 나누고, 나누어진 각 부분 값을 모두 더하거나 보수 취해 더하여 레코드 주소 결정
기수 변환 (Radix Transformation)	- 주어진 키 값을 어떤 특정한 진법 수로 간주하여 다른 진법으로 변환한 후 레코드 주소 구함

 

• 오버플로우 발생 시 해결방안

구분	내용	그림
선형 검색법	- 충돌 발생한 다음 위치에서 차례로 검색하여 첫 번째 빈 공간에 저장 - 레코드 전체 개수 미리 예측 가능할 경우 적용 가능한 방법
체인법 (Chain)	- 오버플로 발생한 레코드를 별도 버킷으로 연결하여 저장 - 링크 위한 오버헤드 발생, 레코드 개수 예측하기 어려울 경우 적용 가능
다중 해상법 (확장 해상)	- 키의 처음 비트 이용하여 디렉토리 접근하는 방식. 디렉토리 통해 버킷 접근 가능 - 버킷에 오버플로 발생할 경우 새로운 버킷 생성하고 디렉토리 포인터 변경하거나 디렉토리 확장

 

* 인덱스 조작

• DB 사용자가 인덱스에 대해 조작할 수 있는 방법
• 인덱스 생성
  • CREATE [UNIQUE] INDEX <인덱스 이름> ON <테이블 이름> (<컬럼(들)>);
  • 예) 고객(CUST) 테이블에 컬럼1, 컬럼2에 대한 인덱스 CUST_IX_01 생성
    • CREATE INDEX CUST_IX_01 ON CUST (컬럼1, 컬럼2);
  • 요소 ▼

파라미터	내용	비고
[UNIQUE]	인덱스 컬럼에 중복 값 허용 안함	CREATE 테이블에서 사용하는 UNIQUE 제약 조건과 동일 의미
<인덱스 이름>	인덱스 이름
<테이블 이름>	인덱스 대상 테이블 이름
<컬럼들>	인덱스 대상ㄷ 테이블 특정 컬럼 이름(들)	복수 컬럼 지정 가능

 

• 인덱스 삭제
  • DROP INDEX <인덱스 이름>;
  • 예) 고객(CUST) 테이블 인덱스 CUST_IX_01
    • DROP INDEX CUST_IX_01;
  • <인덱스 이름> 은 '삭제 대상' 인덱스 이름 의미. 테이블 기재 안함
• 인덱스 변경
  • ALTER [UNIQUE] INDEX <인덱스 이름> ON <테이블 이름> (<컬럼(들)>);