[ByteByteGo] Database Indexing Strategies(데이터 베이스 인덱스 전략)

도입부

잘못 설계된 인덱스나 인덱스의 부재는 데이터베이스 어플리케이션 병목 현상의 주요 원인이다.

 

효율적인 인덱스를 설계하는 것은 우수한 데이터베이스 및 어플리케이션 성능을 달성하는데 필수적이며 데이터베이스 규모가 커질수록 데이터를 검색하고 조작하는 효율적인 방법을 찾는 것이 점점 중요해진다.

 

잘 설계된 인덱싱 전략은 이러한 효율성을 달성하기 위한 핵심 열쇠로 해당 글에서는 어플리케이션 요구사항을 충족하는 효과적인 인덱스를 설계하는 데 도움이 되는 사례를 설명하며 이해를 할것이다.

 

인덱스(index)

인덱스는 책 뒷면에 있는 색인과 마찬가지로 데이터 검색 작업의 속도를 높여주는 자료구조이다. 색인이 정보를 빠르게 찾을 수 있도록 키워드와 페이지 번호를 함께 나열하는 것처럼 데이터베이스 인덱스도 테이블의 모든 행을 스캔할 필요 없이 데이터 검색 속도를 높여주는 유사한 역할을 한다.

 

 

데이터베이스 인덱스의 구조는 정렬된 값의 리스트를 포함하며 각 값은 해당 값이 존재하는 데이터 페이지로 안내하는 포인터와 연결되어 있다.

 

인덱스는 대부분 디스크에 저장되며 데이터 검색 속도를 높이기 위해 특정 테이블과 연계가된다.

• 여기서 말하는 특정 테이블은 Index Segment라는 테이블로 저장이되며 인덱스로 지정된 컬럼 값 + 실제 데이터가 있는 주소

 

인덱스를 구현하기 위해 B-트리, 비트맵, 해시 맵과 같은 다양한 자료 구조를 사용할 수 있다 하지만 관계형 데이터베이스에서 인덱스는 B-트리의 변형인 B+트리 구조로 저장된다. 이러한 구조로 데이터베이스는 관련된 행을 효율적으로 찾을 수 있다.

 

또한 인덱스는 컬럼 수가 적은 좁은 인덱스는 디스크 공간과 유지보수 비용을 절약하는 반면, 넓은 인덱스는 더 광범위한 쿼리를 지원한다.

 

B-트리(B- Tree)

B-트리는 정렬된 데이터를 유지하고 효율적인 삽입, 삭제, 검색 작업을 가능하게 하는 자가 균형 트리 자료 구조로

모든 리프(leaf) 노드가 동일 레벨에 존재하며 이러한 요소가 트리를 균형 잡힌(balanced) 상태로 만들 수 있다.

모든 노드에는 키(key) + 해당 키에 대한 데이터 값(value)를 가지고 있다.

 

루트 노드를 제외한 모든 노드는 d(트리의 최소 차수)에서 2d 사이의 개수의 자식 노드를 가질 수 있으며 루트 노드는 최소 2개의 자식을 가진다.

 

자식이 k개인 비리프(non-leaf) 노드는 k-1개의 키를 포함한다

• 만약 [70, 80]의 키가 존재한다면 70보다 작은 값들은 왼쪽 자식 노드 70과 80사이의 값들은 중간 자식 노드 80보다 큰 값들은 오른쪽 자식 노드에 삽입할 수 있다.

B-트리는 디스크 액세스 횟수를 최소화하도록 설계되었기 때문에 메인 메모리에 수용할 수 없을 정도로 큰 데이터를 저장하는데 탁월한 자료 구조이다.

• B트리는 여러개의 자식 노드(차수)를 가질 수 있기 때문에 트리의 높이를 적게 가져갈 수 있어 디스크 액세스를 낮출 수 있다.

또한 트리가 균형을 이루고 모든 리프 노드가 동일한 깊이에 있기에 조회 시간이 일관되고 예측 가능하다.

 

B-Tree 기본 구조

 

B+트리(B+tree)

B-트리의 변형으로 데이터 포인터(실제 레코드에 대한 포인터)는 오직 리프 노드에만 저장이되며 내부 노드는 오직 키와 다른 노드에 대한 포인터만 포함된다

이는 내부 노드에 훨씬 더 많은 키를 저장할 수 있음을 의미하며 결과적으로 트리의 전체 높이를 줄여주며 이로 인해 디스크 액세스 횟소가 감소한다.

 

모든 리프노드는 연결리스트로 함께 연결되어 있으며 이로 인해 범위 쿼리가 효율적이다 

• 범위의 첫 번째 노드에 접근한 다음, 연결리스트를 순서대로 따라가기만 하면 나머지를 모두 가져올 수 있기 때문

 

B+트리에서 모든 키는 내부 노드에 한번, 리프 노드에 한번으로 총 두 번 나타나며 내부 노드의 키는 찾고자 하는 값이 어느 서브트리에 있을지 결정하는 기준점 역할을 한다.

 

이러한 특징으로 B+트리는 메인 메모리에 다 담을 수 없을 정도로 방대한 양의 데이터를 가진 시스템에 잘 맞으며 데이터는 오직 리프 노드에서만 접근할 수 있기 때문에, 모든 조회의 경우 루트에서 리프까지의 경로 탐색을 거쳐야 하기에 모든 데이터 접근 작업은 일관된 시간이 소요된다.

• B-Tree는 노드의 위치에 따라 엄청 빠르거나 엄청 느리거나 평균일 것이다 하지만 B+Tree는 데이터가 무조건 리프 노드에 위치해 있기에 동일한 시간이 걸린다.

B+Tree 기본 구조

 

속성(Attribute)	B-트리(B-Tree)	B+트리(B+Tree)
구조	리프 노드와 내부 노드 모두 키와 데이터를 저장한다.	오직 리프 노드만 데이터, 데이터포인터를 저장하고 내부 노드는 키만 저장한다.
데이터 접근성	리프 노드와 내부 노드 모두에서 데이터에 직접 접근할 수 있다.	데이터는 오직 리프 노드까지 탐색해 내려가야 접근이 가능하다.
효율성	데이터가 모든 노드에 분산되어 있어 범위 쿼리(Range Query)시 효율성이 떨어질 수 있다.	모든 데이터가 리프 노드에 모여있고 리프 노드끼리 연결되어 있어 범위 쿼리에 훨씬 효율적이다.
삽입 및 삭제	데이터가 모든 노드에 분산되어 있어 작업이 다소 복잡할 수 있다.	데이터가 리프 노드에만 존재하므로 잦은 재정렬 필요성이 줄어들어 약간 더 효율적이다.
공간 활용도	모든 노드가 데이터를 저장하므로 인덱스 공간 활용 효율이 떨어질 수 있다.	데이터가 리프 노드에만 저장되므로 내부 노드의 공간 활용도가 더 높다.
주요 용도	데이터 검색이 주로 특정 키를 타깃으로 하는 데이터베이스 시스템에 유용하다.	범위 쿼리가 더 빈번하게 발생하는 데이터베이스 및 파일 시스템에서 더 흔히 사용된다.

 

클러스터형 인덱스(Clustered Index)

클러스터형 인덱스는 테이블의 레코드가 물리적으로 저장되는 방식을 정렬하며 행을 무작위로 저장하거나 데이터가 삽입된 순서대로 두지 않는다. 

 

대신 인덱스 순서에 맞춰 행들을 물리적으로 모아서 정렬하며

이 순서를 정하는 데 사용되는 특정 컬럼 또는 컬럼 집합을 클러스터형 키(clustered key)라고 부른다. 이러한 정렬 방식이 디스크 상에 데이터가 저장되는 실제 물리적 순서를 결정한다.

 

물리적 데이터 행은 하나의 순서로만 정렬될 수 있기에 테이블 당 단 하나의 클러스터형 인덱스만 존재할 수 있다. 클러스터형 인덱스를 추가하거나 변경하는 것은 데이터 행을 물리적으로 모두 재정렬해야 하므로 시간이 오래 걸릴 수 있다.

 

이러한 이유로 클러스터형 키를 신중하게 선택하는 것이 중요하며 일반적으로 새로운 데이터를 삽입할 때 중복 입력을 피하고 페이지 분할을 최소화하기 위해, 고유하고 순차적으로 증가하는 키를 선택하는 것이 유리하다.

 

이러한 이유로 많은 데이터베이스에서 별도의 클러스터형 인덱스르 명시하지 않으면 기본 키 제약 조건에 의해 해당 컬럼에 클러스터형 인덱스가 자동으로 생성되는 이유이다.

클러스터형 인덱스

 

예외로 PostgreSQL은 클러스터형 인덱스나 다른 인덱스를 기준으로 정렬되지 않고 기본적으로 삽입된 순서대로 저장된다. 다만 테이블의 물리적 데이터를 특정 인덱스와 일치하도록 재정렬하는 CLUSTER 명령어를 제공한다.

 

하지만 데이터가 삽입되거나 업데이트될 때 물리적 정렬이 자동으로 유지되지 않으며 CLUSTER 명령어를 주기적으로 실행해야 순서가 유지된다.

 

비클러스터형 인덱스(Non-clustered Index)

비클러스터형 인덱스는 아까 언급한 색인과 유사하며 데이터 행과 분리된 별도의 키 값 리스트를 유지하며, 각 키는 해당 값을 포함하는 실제 행의 위치를 가르키는 포인터를 가진다.

 

이 포인터들이 인덱스 항목을 실제 데이터 페이지로 연결해 준다. 비클러스터형 인덱스는 데이터 행과 별도의 공간에 저장되므로, 데이터의 물리적 저장 순서가 인덱스로 정한 논리적 순서가 일치하지 않는다.

 

이러한 분리 구조 때문에 비클러스터형 인덱스로 데이터에 접근할 때는 최소 두 번의 디스크 읽기 작업(인덱스 조회에 한 번, 실제 데이터 조회에 한번)이 필요하며 총 2번 조회를 한다.

 

이는 인덱스 데이터가 물리적으로 한데 묶여 있는 클러스터형 인덱스와 대조적으로 비클러스터형 인덱스의 큰 장점은 하나의 테이블에 여러 개를 생성할 수 있어 각기 다른 유형의 쿼리에 최적화를 할 수 있다는 점이다.

 

• 장점
  • 클러스터형 인덱스에 포함되지 않는 컬럼을 조건으로 사용하는 쿼리에 유용(클러스터형 키를 사용하는 쿼리는 굳이 비클러스터형 인덱스를 사용할 필요 x)
  • 넓은 범위의 데이터가 스캔할 필요가 없는 쿼리의 성능을 향상시킴(range 쿼리의 경우 여러번 참조해야함)
• 단점
  
  • 읽기 작업의 속도를 높이지만, 테이블의 데이터가 수정될 때마다 관련된 모든 인덱스를 함께 업데이트해야 하므로 쓰기 작업 속도를 떨어뜨릴 수 있다.

비클러스터링 인덱스의 구조

 

여러가지 인덱스 유형

기본 인덱스(Primary Index)

데이터베이스 기본 인덱스는 대부분 데이터에 접근하는 수단으로 테이블을 생성할때 기본 키(Primary Key)는 흔히 클러스터형 인덱스의 역할도 한다.

덕분에 기본 키로 데이터를 검색할 때 매우 빠른 속도가 보장된다. 이 구성의 효율성은 기본 키가 어떤 형태냐에 따라 크게 좌우되며 만약 키가 순차적으로 증가하는 형태라면 테이블에 데이터를 쓰는 작업이 대체로 효율적이다.

 

But 키가 순차적이지 않다면(무작위 값등) 정렬 순서를 유지하기위해 페이지 병합, 분할등 작업을 하기에 재정렬 작업을 할 수 있으며 이러한 이유로 쓰기 효율성을 저하시킨다.

 

기본 인덱스 구조

 

보조 인덱스(Secondary Index)

기본키가 아닌 다른 컬럼을 기준으로 데이터를 필터링하거나 정렬하는 쿼리는 다른 인덱스를 사용해야 성능향상을 기대할 수 있다.

 

보조 인덱스는 메인 테이블의 레코드를 참조하는 정렬된 구조로 기본 인덱스와 달리 항상 비클러스터형 인덱스로 작동한다.

 

언급했던 클러스터형 인덱스로 작동하기에 메인 테이블의 실제 레코드를 가르키는 포인터와 키 값 쌍의 리스트를 별도로 유지하며 읽기 작업의 속도는 높여주지만 쓰기 작업은 느릴 수 있다.

• 데이터가 새로 쓰이거나 갱신되는 경우 해당 데이터를 바라보는 모든 인덱스 구조를 함께 갱신하기 때문

보조 인덱스 구조

 

복합 인덱스(Composite Index)

복합 인덱스는 인덱스 키에 두 개 이상의 컬럼을 묶어서 구성하는 인덱스이다. 이 유형은 특정 컬럼 세트를 조합하여 데이터를 필터링하거나 정렬하는 쿼리에 특히 효과적이다.

 

• 예를 들어 where 조건문으로 이름과 나이를 사용한 검색 쿼리를 자주 실행한다고 했을때 이름과 나이에 각각 별도의 인덱스를 2개를 만드는 것보다 두 컬럼을 하나로 묶은 단일 복합 인덱스를 만드는 것이 더 좋다.

복합인덱스에서 가장 핵심부분은 컬럼의 배치 순서로 복합인덱스는 첫번째 컬럼을 기준으로 먼저 정렬되어 있기에 데이터를 가장 좁은 범위로 필터링해 줄 수 있는(선택도가 높은)컬럼을 인덱스의 앞 순서에 배치하는 것이 좋다.

 

But 많은 컬럼을 묶을수록 복합 인덱스의 크기가 비대해져 더 많은 저장 공간을 차지하게 된다.

 

복합 키 인덱스 구조

 

커버링 인덱스(Covering Index)

작성한 쿼리문이 요구하는 컬럼이 기존 인덱스 페이지 안에 있을때 클러스터링 인덱스 페이지를 참조하지 않고 바로 인덱스 페이지에서 결과를 반환하는 방법

 

테이블 접근 단계를 생략하고 인덱스만으로 쿼리를 조회할 수 있으므로 디스크I/O 작업이 줄어들어 특정 쿼리의 속도가 향상된다.

대형 테이블에서 적은 수의 컬럼 정보만 가져오면서 대량의 행을 반환하는 쿼리를 처리할 때 더욱 효과적이다.

 

커버링 인덱스 역시 쓰기 작업 시 추가적인 오버헤드가 발생한다.

• 너무 많은 종류의 쿼리를 커버하려고 인덱스에 컬럼을 과도하게 추가하면 크기가 커져 스토리지 부담이 증가한다.

 

커버링 인덱스 구조

 

유니크 인덱스(Unique Index)

유니크 인덱스는 인덱스로 지정된 키 값들이 데이터베이스 내에서 유일함을 보장한다.

데이터의 무결성을 강제하고 중복 데이터가 들어오는 것을 원천 차단하는 데 자주 사용된다.

 

고유 인덱스는 완전히 동일한 키 값을 가진 두 개 이상의 행이 존재하는 것을 금지함으로써 작동하며 이미 존재하는 데이터와 똑같은 인덱스 키 값을 가진 신규 레코드를 삽입하려고 하면 데이터베이스가 에러를 내며 이를 차단한다.

 

• 서비스에서 이메일로 인증을 받고 하나의 계정에 하나의 이메일만 사용되어야 한다면 이메일행에 유니크 인덱스를 추가하는 것이 좋다.

 

이메일 컬럼에 유니크 인덱스를 설정했을때 중복 데이터를 삽입을 하려는 경우 실패한다.

 

필터링 인덱스(Filtered Index)

예시로 회원 테이블의 데이터가 1000개가 있고 950개가 탈퇴한 회원이고 나머지 50개가 실제 사용하는 유저라고 가정했을때 회원테이블에 접근하기 위해서 인덱스를 생성한다고 가정했을때

기본키로 인덱스를 잡으면 실제 사용하는 사람이 50명밖에 안되지만 나머지 950명에 대해서 인덱스 정보가 낭비가 되는 꼴이다.

따라서 status = "Active"로 인덱스를 설정해서 활성화된 사용자들만 빠르게 찾을 수 있도록 설정할 수 있다.

 

즉 전체 데이터가 아닌 데이터의 특정 하위 집합(조건)에만 필터를 걸어, 원하는 범위나 특정 값 세트에 대해서만 인덱스를 생성하는 방식이다.

 

대형 테이블에서 특정 조건에 부합하는 일부 데이터만 자주 조회될 때, 인덱스 크기를 작게 유지하면서 쿼리 성능을 향상시키고 저장공간도 절약할 수 있다.

 

필터링 인덱스는 관계형 데이터베이스 중 MicrosoftSQL, PostgreSQL은 필터링된 인덱스를 지원하지만 MySQL은 지원하지 않는다.

 

Country 컬럼이 대부분 US 값으로 구성되어 있는경우 필터링 인덱스를 Country = "US"로 설정할 수 있다.

 

특수 인덱스(Specialized Indexes)

모든 DBMS에서 다 지원하지 않지만 알맞은 상황을 만나면 좋은 효율을 발휘할 수 있으며 대부분 일반적인 B+tree 인덱스를 사용하지 않는다.

비트맵 인덱스(Bitmap Index)

비트맵 인덱스는 0과 1로 이루어진 비트 배열(비트맵)을 사용하는 특수한 데이터베이스 인덱스이다.

고유한 값의 가짓수가 얼마 되지 않는, 즉 기수성(중복되지 않는 고유한 성질)이 낮은 컬럼을 처리할때 좋은 효과를 낸다.

 

• 성별, 예/아니요 처럼 Enum이나 플래그 컬럼이 좋은 대상이다.

비트맵 인덱스에서는 컬럼의 고유 값마다 각각 하나의 비트맵이 할당되며 비트맵 내부의 비트 개수는 테이블의 총 행(row)수와 같다.

해당 행의 컬럼 값이 일치하면 비트를 1로, 일치하지 않으면 0으로 세팅하는 방식이다

 

컬럼의 값 종류가 적을때 이러한 방식은 저장 공간을 적게 먹으므로 매우 효율적이며 비트맵 인덱스는 하드웨어 친화적인 비트 연산을 직접 활용할 수 있어서 여러 조건이 뒤섞인 복잡한 쿼리를 빠르게 처리할 수 있다.

 

BUT 읽기 작업은 매우 빠르지만 쓰기(업데이트) 작업 시에는 비트맵 내부의 비트들을 일일히 찾아서 뒤집어야 하기에 성능이 떨어질 수 있다.

 

따라서 데이터 변화가 거의 없는 정적인 테이블이나 읽기 전용인 데이터 웨어하우스(DW) 환경에 적합하다.

 

비트맵 인덱스를 사용하여 읽기 최적화

 

대표적으로 Oracle, IBM Db2, SQL Server 등이 비트맵 인덱스를 지원하는 시스템이며 MySQL과 PostgreSQL은 비트맵 인덱스를 지원하지 않는다.

 

공간 인덱스(Spatial Index)

공간 인덱스는 지리적 좌표, 다각형(폴리곤), 3차원 입체와 같은 다차원 객체 데이터를 인덱싱하기 위해 만들어진 특수 인덱스로 해당 인덱스는 가장 가까운 이웃 위치 찾기, 반경 내 지역 검색 같은 공간 쿼리의 속도를 내기 위해 고안되었다.

 

공간 데이터의 특성상 인덱스가 없다면 기하학적 연산량이 너무 많아 컴퓨터에 엄청난 부담을 주게 된다.

 

B-tree 같은 기존 인덱스 방식은 일차원적인 선형 데이터(숫자, 문자열 등)을 다루도록 설계되었기에 면적과 다차원을 다루는 공간 데이터 처리에는 한계가 있다.

 

이러한 한계를 극복하기 위해 공간 데이터를 효율적으로 저장하고 찾기 위해 최적화된 R-tree나 쿼드트리 등의 알고리즘을 사용한다.

 

R-tree

R-tree의 R은 Rectangle로 최소 경계 사각형(Minimum Bounding Rectangle)로 공간을 분리한다.

 

모든 노드는 자식 노드들에 포함된 모든 공간 객체를 감싸는 MBR로 MBR끼리 겹칠 수도 있고 부모 MBR은 자식 MBR을 포함하는 트리 구조로 이룬다.

 

 

위 사진처럼 이웃한 노드들의 바운딩 박스는 서로 면적이 겹칠 수 있다.

 

위치 검색 쿼리가 들어오면 R-트리는 검색 영역과 전혀 교차하지 않는 바운딩 박스들을 단번에 걸러내어 불필요한 많은 행들을 탐색 대상에서 제외한다.

 

이러한 방식으로 인해 테이블 전체를 모두 뒤지는 것보다 훨씬 효율적으로 공간을 조회할 수 있다.

 

• 예시로 특정 좌표 중심의 반경 Nkm 이내 맛집 찾기, 현재 위치에서 가장 가까운 지하철역 조회 기능이 핵심인 지도 앱 데이터베이스에서 R-트리 인덱스는 효과적으로 기능을 사용할 수 있다.
• 또한 우리가 하려는 택시 동승 프로젝트에서도 사용자 기반의 위치(출발점)과 도착점을 기준으로 0 ~ 200m 반경의 클러스터를 생성하여 출발점과 도착점 클러스터와 겹치는 승객이 있을경우 자동으로 매칭을 해서 위치를 기준으로 중간지점을 산출하여 동승할 수 있도록 서비스를 구성하면 어떨까 생각했다.

 

공간 인덱스는 많은 관계형 데이터베이스에서 지원하며 MySQL, PostgreSQL(PostGIS 사용), Oracle, SQL Server 등 모두 공간 인덱싱 기능을 지원한다.

 

 

전체 텍스트 인덱스(full-text Index)

전체 텍스트 인덱스는 텍스트 컬럼 안의 수많은 문자열 중 임의의 위치에 들어 있는 키워드를 검색하고자 할 때 사용한다.

 

텍스트의 중간 단어 검색이나 부분일치 검색을 시도할 때 B-트리 인덱스는 정확히 일치하거나 범위 정렬된 구조에만 맞춰져 있기에 제 성능을 못낸다.

 

• 뉴스 기사, 도서 본문, 수많은 단어가 뒤섞인 긴 장문의 자유 형식 텍스트 뭉치에서 원하는 단어를 찾을 때 빠르게 찾을 수 있다.
• 또한 우리 프로젝트에서도 지도에서 사용자가 도착지 검색을 하는 경우 작성한 글자에 따라서 일치하는 장소를 드랍다운 할 수 있도록 적용할 수 있을것 같다.

전체 텍스트 인덱스는 컬럼 내 텍스트를 형태소나 단위별 단어(토큰)으로 잘개 쪼갠 후 이 토큰들을 기반으로 인덱스를 새로 빌드한다.

인덱스 내부에는 각 단어들이 어떤 문서의 몇 번째 위치에 등장했는지에 대한 위치 링크 정보가 함께 저장된다.

 

전체 텍스트 인덱스 구현에서 가장 흔히 쓰이는 기술이 역인덱스 구조이며 

 

역 인덱스는 단어나 숫자 같은 실제 contents를 키로 삼아, 그것이 포함된 문서 번호와 위치 목록을 거꾸로 찾아 들어가는 구조를 가진 자료구조이다.

 

기존 페이지 중심구조(정색인 : 특정 페이지에서 그 안에 포함된 단어들)를 키워드 중심 구조(역색인 : 특정 단어가 나타나는 페이지 목록)으로 뒤집었기에 역인덱스라고 부른다.

 

쿼리에 포함된 단어들이 들어있는 문서 집합들을 인덱스에서 끄집어낸 뒤, 그 집합들의 교집합을 구하는 방식으로 검색어들이 전부 들어있는 문서를 빠르게 도출하며

 

MySQL, PostgreSQL, SQL Server 같은 전통적인 관계형 데이터베이스 계열에서도 지원된다.

 

하지만 데이터가 커지고 검색이 주요 기능이라고 한다면 DB에는 저장, 삭제, 갱신만을 사용하고 조회할때만 ElasticSearch를 사용해서 오버헤드를 빠르게 접근할 수 있다.

 

하지만 전체 텍스트 인덱스가 검색 속도를 올려주는 대신, 인덱스 용량 자체가 커질 수 있고 데이터 삽입, 수정 시 상당한 성능 저하(오버헤드)를 감수해야 한다.

 

ElasticSearch

ElasticSearch는 강력한 텍스트 검색 라이브러리인 Apache Lucene를 뼈대로 삼으며, 실시간 애플리케이션의 대규모 확장이 가능하도록 분산 시스템 기능을 얹어 성능을 극대화한 제품이다.

 

해시 인덱스(Hash Index)

해시 인덱스는 해시 함수를 이용해 키 값을 인덱스 내의 고유한 물리적 주소로 다이렉트 매핑함으로써 데이터 검색 속도를 빠르게 하는 인덱스 유형이다.

 

이러한 방식은 검색 조건이 인덱스 키와 정확히 맞아떨어지는 동등 비교(=) 연산에 최적화가 되어 있다

 

동작원리는 해시 함수가 들어오는 고유 키 값마다 고유한 해시 값을 만들어내고 그 해시 값 자체가 실제 데이터 레코드가 저장된 위치를 가리키는 포인터로 직접 사용된다.

 

탐색시 데이터베이스가 검색 키의 해시 값을 계산하여 레코드 위치로 단번에 접근하므로, 순차 스캔이나 B-트리의 노드 경로를 타고 내려가는 복잡한 과정 없이 즉각적인 조회가 가능하여 O(log N)에서 O(1)로 조회할 수 있다. 

 

하지만 해시 인덱스는 내부 데이터를 정렬된 순서로 보관하지 않기에 키의 대소 관계나 위치에 의존하는 부등호(<, >)연산 조건에는 사용할 수 없기에 범위기반 쿼리에는 해시 인덱스를 사용할 수 없다.

 

PostgreSQL은 해시 인덱스를 정식한다.