인덱싱, 해싱, 자료구조 측면에서의 해싱, 순서 인덱스, 해싱 인덱스

 

 

• 인덱싱이란, 데이터를 검색할 때 발생하는 비효율적인 문제들을 해결하기 위한 방법으로 인덱스를 설계하여 생성하는 것을 말한다. 여기서 인덱스란, 특정 레코드에 빠르게 접근할 수 있게 하는 데이터 관련 구조를 의미한다. DBMS는 이 인덱스를 이용하여 레코드가 디스크 저장장치나 메모리의 어느 블록에 저장되어 있는지 알아내고 그 블록을 읽는다. 인덱스는 크게 순서 인덱스(Ordered Index)와 해시 인덱스(Hash Index)로 나눌 수 있다. 순서 인덱스란 검색 키가 순서대로 저장되어 있으며, 해시 인덱스는 검색 키가 버킷들에 해시 함수를 이용하여 분산 저장되어 있다. 검색 키 (Search Key)란, 파일에서 레코드를 찾는 속성(attribute)을 말한다. 인덱스 엔트리는 이 검색키와 포인터로 이루어져 있다. 포인터는 검색 키에 대응되는 하나 이상의 레코드에 대한 포인터를 의미하며, 레코드가 저장되어 있는 메모리/디스크 블록의 식별자와 블록 안에서 레코드를 인식하기 위한 오프셋으로 구성되어 있다. 인덱스 파일은 원본 파일에 비해 사이즈가 훨씬 작다.

 

• 순서 인덱스는 밀집 인덱스(Dense Index)와 희소 인덱스(Sparse Index)로 다시 분류할 수 있다. 밀집 인덱스는, 모든 레코드에 대해 인덱스 엔트리(검색 키와 포인터 쌍)를 유지하는 반면에, 희소 인덱스는 소수의 인덱스 엔트리만 유지한다. 현재 널리 사용되는 대표적인 순서 인덱스로 Knuth가 제안한 B* 트리 인덱스가 있다.

 

• 순서 인덱스를 이용해서 데이터에 접근할 경우, 트리 구조를 이용하므로 이진 검색이 필요해진다. 이로 인해 입출력 연산이 많이 일어나서 속도의 저하를 불러오므로 해싱 인덱스 방법이 필요해진 것이다. 자료 구조에서 사용되는 해싱의 개념은, 검색 키 값에 직접 산술 연산을 적용하여 데이터가 저장되어 있는 버킷 주소를 계산해서 데이터에 접근하는 것을 말한다. 이 때 해시 함수는 검색 키를 입력으로 받아서 버킷 주소를 결과 값으로 반환한다. 검색 키 값을 물리적인 주소로 맵핑시키기 때문에 사상 함수(Mapping function)라고도 한다. 여기서 버킷이란, 하나의 주소를 가지면서 한 개 이상의 레코드를 저장할 수 있는 메모리 공간 범위를 말하는 것으로, 여러 개의 슬롯(slot)으로 구성된다. 하나의 슬롯에는 하나의 레코드가 저장된다. 이 때, 서로 다른 두 개의 검색 키 값이 동일한 주소의 버킷에 대응될 수 있는데 이를 충돌(Collision)이라고 하며, 같은 버킷 주소를 갖는 레코드들을 동거자(synonym)라고 한다. 좋은 해시 함수란 이러한 충돌이 적게끔 레코드들이 고르게 분포되도록 주소를 생성해야 하며 계산이 빨라야 한다. 버킷에 레코드를 저장할 수 있는 여유 공간이 없을 때 오버플로가 발생하며, 많이 발생할수록 레코드 접근 시간이 길어져서 성능이 저하된다. 이러한 해싱 방법을 기반으로 해서 만들어진 파일을 직접 파일(Direct file)이라고 한다.

 

• 자료 구조 및 데이터베이스 측면에서의 해싱은 정적 해싱과 동적 해싱으로 나눌 수 있다. 정적 해싱(Static hashing)이란, 저장 공간의 단위인 버킷 개수가 고정된 해싱 방법을 말한다. 즉, 데이터를 입력 받기 이전에 일정 크기의 메모리를 미리 할당 받아야 한다. 정적 해싱 함수에는 Mid Square, Division, Folding 방법 등이 있다. 중간 제곱 함수(Mid Square)는, 검색 키 값을 제곱한 후에 중간의 몇 비트를 이용해서 버킷 주소를 생성한다. 제산 함수(Division)는 검색 키 값을 소수로 나눈 나머지를 버킷 주소로 사용한다. 접지 함수(Folding)는 키 값을 동일한 길이의 여러 부분으로 분할하여, 그 부분을 더해서 버킷 주소로 사용한다. 이러한 정적 해싱의 문제점은 역시, 충돌과 오버플로이다. 이를 해결하기 위한 방법으로는, 개발 주소법(선형 조사법, 2차 조사법, 임의 조사법, 재해싱), 체인 이용법 등이 있다. 선혛 개방 주소 지정법이란, 충돌이 일어난 그 위치에서 테이블 순으로 검색하여 나온 첫번째 빈 버킷 공간에 레코드를 저장하는 것을 말한다. 체인 이용법은, 충돌이 발생한 레코드들을 연결하는 방법으로, 해시 테이블에서 포인터를 배열로 만들고, 그 포인터에 레코드들을 체인으로 연결한다. 즉, 충돌이 발생하는 동거자들끼리 연결 리스트를 구성하는 것이다.

 

• 정적 해싱은, 너무 작은 공간을 잡을 경우 충돌의 문제가 있고, 미리 큰 공간을 잡을 경우에는 초기에 많은 크기의 공간이 낭비된다. 반면에 동적 해싱(Dynamic hashing)은, 동적으로 저장 공간의 크기가 증가 및 감소할 수 있도록 하는 방법으로, 오버플로 발생 문제를 해소하기 위해 주소 공간의 크기를 동적으로 변화시킨다. 공간 동적 해싱의 한 형태로 확장성 해싱(Extensible hashing)이 있다.