해쉬 인덱스는 해쉬 함수(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')에는 효과가 없다.

아래와 같이 두 개 이상의 필드를 이용해서 인덱스를 구성하는 것을 복합 인덱스(Composite index)라고 한다. 인덱스는 검색키와 주소의 쌍으로 구분되며 이를 인덱스 엔트리(Index Entry)라 부르는데, 복합인덱스는 검색키 N개와 주소의 쌍이 인덱스 엔트리가 되는 것이다.

이 때, 인덱스는 대소관계에 의해 검색키1을 우선 정렬하고 검색키1에 대해여 검색키2를 정렬하는 방식으로 구성된다. 예를 들어, 아래 좌측과 같은 테이블이 있고 A와 B컬럼을 복합 인덱스로 하면,  아래 우측과 같이 인덱스가 만들어 지는 것이다.

A컬럼과 B컬럼의 인덱스가 각각 만들어져 있다면,  select * from 테이블 where A컬럼='1001' and B컬럼='2' 라는 질의를 날렸을 때, A컬럼='1001'의 조건으로 참조된 결과와 B컬럼='2'의 조건으로 참조된 결과를 비교하여 중첩된 레코드를 찾을 것이다. 하지만 복합 인덱스로 구성했을 경우에는 두 조건을 만족하는 레코드를 하나의 인덱스로 처리할 수 있어서 효율적이다. 

또한 select B컬럼 값 from 테이블 where A컬럼='1001' 처럼 원본 데이터에 접근하지 않고도 복합 인덱스내에서 바로 질의 처리가 가능해지는 경우도 있다.

단, 필드의 순서에 따라 인덱스 효과가 달라지기 때문에 주의를 요한다. 

예를 들어,

select * from 테이블 where  A컬럼 = '1001' and B컬럼 > '2' 와 

select * from 테이블 where  A컬럼 > '1001' and B컬럼 = '2'라는 질의를 날린다고 해보자. 

첫 번째 질의는 A컬럼 키 1001을 찾은 뒤 제한 된 B 컬럼의 검색키를 검색하면되지만, 두 번째 질의는 A컬럼 > '1001'을 만족하는 검색키를 모두 검색하면서 B컬럼='2' 조건을 조회하기 때문에 효율적으로 동작하지 않는다. 따라서 두번째 질의를 잘 처리하기 위해서는 (B컬럼, A컬럼)의 순서로 구성된 필드 집합으로 복합 인덱스를 생성해야 한다.

결국 복합 인덱스를 만들 때는 자주 사용되는 질의 유형을 사전에 분석하여 결정해야 하는 것이다.

DB에서 데이터에 대한 접근은 결국 디스크 I/O라는 뜻이다. 디스크를 헤드를 위치시키고, 디스크를 회전하고, 데이터를 전송하고... CPU만큼이나 빠르게 작동하지 않는다. 때문에 검색의 효율을 높이기 위해서 인덱스를 설정한다. 이 인덱스의 방식 중 가장 널리 사용되는 방식이 B+트리 인덱스이다.

차수가 N인 B+트리의 노드 구조는 위와 같이 N개의 포인터와 N-1개의 검색키의 집합으로 구성되어 있다.  

키는 Key i-1 < Key i < Key i+1 ... 의 관계를 가지고 있으며, Key i와 Key i+1 사이에 있는 포인터인 P i+1이 가리키는 하위 노드 집합에는 Key i보다는 크고 Key i+1보다는 작거나 같은 검색키들이 위치해 있다. 

레코드가 10만 개인 테이블에서 특정 레코드를 검색한다고 했을 때, 인덱스가 구성되어 있지 않다면 최악의 경우 10만 건을 전부 스캔해야 한다. 반면, 차수가 10인 B+트리로 구성했을 경우 아래와 같이 구조가 형성되기 때문에 최악의 경우에도 10개의 키를 4번 검색하는 것만으로 원하는 레코드를 찾을 수 있다. 

대략적으로 시간복잡도가, O(N)에서 O(logN)으로 향상되는 셈이다.