SQL 데이터베이스(DB) 해시 인덱스, 버켓, 해시 함수

해시 인덱스(hash index)

- 해시 함수를 기반으로 인덱스 엔트리를 저장한 인덱스

 

버켓

º 인덱스 엔트리가 저장되는 공간

º 해시함수 값을 버켓 번호로 사용

✔  해시함수 값으로 인덱스 엔트리를 저장할 버켓을 결정

 

인덱스 구성 방법

- 인덱스 구성에 사용될 검색 키 필드 결정

- 레코드의 필드 값에 해시 함수를 적용하여 버켓 번호 생성

- 인덱스 엔트리 (필드 값과 레코드 주소 쌍)를 생성하여 해당 버켓에 저장

 

인덱스 사용 방법

- 검색할 필드 값을 해시 함수에 적용하여 버켓 번호 생성

- 해당 버켓 안에 들어 있는 인덱스 엔트리들 중 원하는 필드 값을 포함한 엔트리 검색

- 엔트리에 포함된 레코드 주소 이용

 

해시 함수

✔ 대량의 데이터 키 집합을 적은 범위의 데이터 집합으로 대응시키는 함수 해시 값은 입력 값의 분포와 상관없이 균등하게 분포되어야 함

 

해시 함수의 예)  H(x) = x % N (나머지 연산)

▪ 1부터 N-1까지의 정수를 해시 값으로 생성

 

버켓 오버플로우

- 일반적으로 버켓의 크기는 고정됨

- 버켓에 엔트리가 다 차는 경우 오버플로우 발생

- 새로운 버켓을 생성하여 기존 버켓과 연결해야 함 (bucket chaining)

- 오버플로우가 많이 발생할 수록 해시 인덱스 성능이 저하됨

 

해시 함수와 버켓 오버플로우

º 해시 함수의 균등성이 좋을수록 오버플로우가 적고, 균등성이 나쁠수록 오버플로우가 빈번함

º 버켓 오버플로우가 많이 발생한 경우 인덱스의 재구성 작업 필요

→ 버켓의 개수를 늘리고 해시 함수를 변경

 

B+ tree 인덱스 or 해시 인덱스

 

해시 인덱스

- 동등 비교 조건을 갖는 검색에 유리

✔ 해시 함수를 통해 직접 인텍스 엔트리를 포함하는 버켓을 찾음

 

B+ tree 인덱스

- 범위 조건을 포함한 검색에 유리

✔ 단말 노드의 엔트리들이 검색 키 순서대로 정렬 및 연결되어 있음

 

인덱스의 분류

 

▷ 대응 밀집도에 따라 분류

 

희소 인덱스(sparse index)

- 테이블의 일부 레코드에 대해서만 인덱스 엔트리 생성

 

밀집 인덱스(dense index)

- 테이블의 모든 레코드에 대해서 인덱스 엔트리 생성

 

▷클러스터링 유무에 따라 분류

 

클러스터 인덱스(clustered index)

- 인덱스가 설정된 필드 값의 순서대로 레코드들이 인접하여 저장됨

▪ 1차 인덱스 – 한 테이블에는 하나의 클러스터 인덱스만 가능

- 주로 기본 키 필드에 대해 설정됨

- 희소 인덱스 또는 밀집 인덱스 형태 가능

 

비클러스터 인덱스(non-clustered index)

- 인덱스 필드 값의 순서가 레코드들의 물리적 저장 위치와 무관

- 2차 인덱스

- 반드시 밀집 인덱스 구조를 가짐