5.4 해시(Hash) 인덱스

5.4.1 구조 및 특성

해시 인덱스의 큰 장점은 실제 키값과는 관계없이 인덱스 크기가 작고 검색이 빠르다는 것이다. 해시 인덱스는 트리 형태의 구조가 아니므로 검색하고자 하는 값을 주면 해시 함수를 거쳐서 찾고자 하는 키값이 포함된 버킷을 알아낼 수 있다. 그리고 그 버킷 하나만 읽어서 비교해 보면 실제 레코드가 저장된 위치를 바로 알 수 있다.

또한 해시 인덱스는 원래의 키값을 저장하는 것이 아니라 해시 함수의 결과만을 저장하므로 키 칼럼의 값이 아무리 길어도 실제 해시 인덱스에 저장되는 값은 4~8바이트 수준으로 상당히 줄어든다. 그래서 해시 인덱스는 B-Tree 인덱스보다는 상당히 크기가 작은 편이다.

해시 인덱스에서 가장 중요한 것은 해시 함수로, 입력된 키값이 어디에 저장될지를 결정하는 함수다. 해시함수의 결과 값의 범위가 넓으면 공간의 낭비가 커지고, 값의 범위가 작으면 충돌이 발생해 인덱스의 장점이 사라진다. 입력 값이 다르지만 해시 값이 같은 경우를 충돌이라고 한다.

5.4.2 해시 인덱스의 가용성 및 효율성

해시 인덱스는 빠른 검색을 제공하지만 키값 자체가 변환되어 저장되기 때문에 범위를 검색하거나 원본값 기준으로 정렬할 수 없다. 해시 인덱스는 이렇게 원본 키값이 변환되어 저장되기 때문에 B-Tree와는 달리 어떤 방식으로도 해시 인덱스를 사용하지 못하는 경우도 발생한다. 각 예제를 통해 해시 인덱스의 효율성을 살펴보자

• 작업 범위 제한조건으로 해시 인덱스를 사용하는 쿼리

동등 비교조건으로 값을 검색하거나 IN 연산자를 통한 검색은 해시 인덱스의 장점을 이용할 수 있다.

• 해시 인덱스를 전혀 사용하지 못하는 쿼리

크다 작다 기반의 검색은 어떠한 방법으로도 해시 인덱스를 사용할 수 없다. 즉 작업 범위 결정 조건뿐 아니라 체크 조건의 용도로도 전혀 사용할 수 없다. 대체로 범위 비교나 부정형 비교는 해시 인덱스를 사용할 수 없다.

5.5 R-Tree 인덱스

Mysql의 공간 인덱스(Spatial Index)는 R-Tree 인덱스 알고리즘을 이용해 2차원의 데이터를 인덱싱 하고 검색하는 목적의 인덱스다.기본적인 내부 매커니즘은 B-Tree와 흡사하다. B-Tree는 인덱스를 구성하는 칼럼의 값이 1차원의 스칼라 값인 반면, R-Tree 인덱스는 2차원의 공간 개념 값이라는 것이다.

Mysql의 공간 확장에는 아래와 같이 크게 3가지 기능이 포함되 있다.

• 공간 데이터를 저장할 수 있는 데이터 타입
• 공간 데이터의 검색을 위한 공간 인덱스(R-Tree 알고리즘)
• 공간 데이터의 연산 함수(거리 또는 포함 관계의 처리)

5.5.1 구조 및 특성

공간 정보의 검색을 위한 R-Tree알고리즘을 이해하려면 MBR이라는 개념을 알고 있어야 한다. MBR 이란 Minimum Bounding Rectangle의 약자로 해당 도형을 감싸는 최소 크기의 사각형을 의미하는데, 이 사각형들의 포함관계를 B-Tree혀테로 구현한 인덱스가 R-Tree 인덱스다.

5.5.2 R-Tree 인덱스의 용도

R-Tree는 위에서 언급한 MBR 정보를 이용해 B-Tree 형태로 인덱스를 구축하므로 Rectangle 의 “R”과 B-Tree의 “Tree”를 섞어서 R-Tree라는 이름이 붙여졌으며, 공간 인덱스라고도 한다. 일반적으로 WGS84(GPS)기준의 위도, 경도 좌표 저장에 주로 사용된다. 하지만 위도, 경도 좌표뿐 아니라 CAD/CAM 소프트웨어 또는 회로 디자인 등과 같이 좌표 시스템에 기반을 둔 정보에 대해서는 모두 적용할 수 있다.

R-Tree는 도형의 포함관계를 이용하므로 Contains() 또는 Intersect() 등과 같은 포함 관계를 비교하는 함수로 검색을 수행하는 경우에만 인덱스를 이용할 수 있다.

5.6 Fractal-Tree 인덱스

인터넷이 발전하면서 데이터의 양이 급증하고 있는데, 하드웨어 성능은 그만큼 따라가지 못하고 있다. 하드웨어 뿐만 아니라 DBMS의 B-Tree 인덱스 알고리즘 또한 한계에 도달한 것으로 보인다.

Fractal-Tree는 아주 최근에 개발된 기술인데, 안타깝게도 독점적인 특허로 등록된 알고리즘이어서 아직 많은 DBMS에 구현되지 못하고 있다. 현재는 TokuTek회사에서 개발된 Mysql 스토리지 엔진 TokuDB에만 적용되 있다.

5.6.1 Fractal-Tree의 특성

B-Tree인덱스에서 인덱스 키를 검색하거나 변경하는 과정 중에 발생하는 가장 큰 문제는 디스크의 랜덤 I/O가 상대적으로 많이 필요하다는 것이다. Fractal-Tree는 이러한 B-Tree의 단점을 최소화 하고, 이를 순차 I/O로 변환해서 처리할 수 있다는 것이 가장 큰 장점이다. 그래서 Fractal-Tree를 스트리밍 B-Tree라고도 한다. Fractal-Tree는 인덱스 키가 추가되거나 삭제될 때 B-Tree인덱스 보다 더 많은 정렬 작업이 필요로 하며, 이때문에 더 많은 CPU 처리가 필요하다. 하지만 인덱스 단편화가 발생하지 않도록 구성할 수 있고, 인덱스 키 값을 클러스터링 하기 때문에 B-Tree보다는 대용량 테이블에서 높은 성능을 보장한다.

5.6.2 Fractal-Tree의 가용성과 효율성

Fractal-Tree의 또 다른 장점은 B-Tree의 장점을 그대로 Fractal-Tree도 가지고 있다는 것이다. 그래서 현재 B-Tree로 생성된 인덱스를 Fractal-Tree로 변경해도 충분히 동일한 효과를 얻을 수 있다. 또한 B-Tree에서 인덱스를 효율적으로 사용하지 못하는 쿼리는 Fractal-Tree에서 적용되더라도 같은 결과를 보인다고 할 수 있기 때문에 별도의 학습이 필요하지 않은 것도 큰 장점이라 볼 수 있다.