해쉬 인덱스

해쉬 인덱스는 해쉬 함수(Hash function)을 기반으로 인덱스의 엔트리를 구성한다. 인덱스 엔트리는 아래 그림과 같이 버켓(bucket)이라고 불리는 공간에 저장되며 각 버켓에 해쉬 함수에 의해 생성된 버켓 번호가 부여된다. 바로 이 버켓들의 집합이 해쉬 인덱스인 것이다. 

해쉬 인덱스를 생성하면 인덱스로 구성하려는 필드 값들을 해쉬 함수로부터 버켓 번호를 부여받아 해당 버켓에 엔트리를 저장한다. 해쉬 인덱스를 사용하여 검색을 할 때도 인덱스를 구성한 필드 값을 해쉬 함수에 적용하여 버켓 번호를 알아낸 뒤 해당 버켓 번호를 가진 버켓 엔트리 중에서 추출하는 것이다.

해쉬 함수는 대규모 데이터 키 집합에 대해서 적은 범위의 데이터 집합으로 대응시키는 함수를 말한다. 대응되는 함수 값(=해쉬 값)은 입력 값의 분포와 상관 없이 균등하게 분포되어야 한다. 가장 간단한 예로는 모듈러 연산을 들 수 있겠다. 예를 들어 해쉬함수 H(X) = X % 3이라고 정의한다면, 인덱스를 구성하고자 하는 컬럼의 값을 3으로 나누어 나머지에 해당하는 값을 버켓 번호로 지정하는 것이다.(아래 예시 참조)

해쉬 함수는 인덱스 엔트리들 각 버켓에 균등하게 할당되도록 짜여져 있겠지만, 입력 값에 따라서 완전히 동일할 수는 없기 때문에 특정 버켓이 오버플로가 발생할 수 있다. 이 경우 버켓의 개수를 늘리고 해쉬 함수를 변경 하는 등의 인덱스 재구성 작업이 필요하다. 

해쉬 인덱스는 B+트리 인덱스에 비해 등동조건 검색(ex select * from 테이블 where A컬럼 ='1001')에 유리하다. B+트리 인덱스는 트리의 높이만큼 검색을 해야하지만, 해쉬 인덱스는 해당 버켓을 찾는데 한 번의 검색이면 되기 때문이다. 하지만 데이터가 순차적으로 저장되지 않고 각 버켓에 나누어 저장되기 때문에 범위조건 질의(ex select * from 테이블 where A컬럼 between '1001' and '2001')에는 효과가 없다.