여러 DBMS에서 사용하는 가장 흔한 인덱스 유형은 B-tree 인덱스다. 여러 DBMS가 해시, 공간(Spatial) 인덱스 같은 추가 타입이나 다른 특별한 구조의 인덱스를 사용하기는 하지만, B-tree 인덱스가 가장 다재다능해서 많이 사용한다. B-tree 인덱스를 자세히 다루는 것은 이 책의 범위를 넘어서지만 간단히 살펴보자. B-tree는 루트 노드에서 시작해 많은 중간 노드를 거쳐 실제 데이터를 가리키는 수많은 리프 노드를 탐색하는 구조로 되어 있다.

쿼리 성능에 대한 B-tree 인덱스의 기여도는 인덱스 유형에 따라 크게 다르다. 인덱스 유형에는 두 가지, 즉 클러스터 인덱스와 비클러스터 인덱스가 있다. 클러스터 인덱스는 인덱스를 만들 때 명시된 컬럼의 순서대로 테이블의 데이터를 물리적으로 정렬한다. 테이블에 있는 로우를 두 가지 이상의 방식으로 정렬하는 것은 불가능하므로 클러스터 인덱스는 테이블당 하나만 만들 수 있다. 적어도 SQL Server에서는 통상 클러스터 인덱스가 데이터를 직접 포함하는 리프 노드를 가진다. 비클러스터 인덱스는 클러스터 인덱스와 구조가 같지만 다음 두 가지 면에서 다르다.

• 비클러스터 인덱스는 테이블 데이터가 쌓인 물리적인 순서와 다르게 정렬될 수 있다.

• 비클러스터 인덱스의 리프 노드는 데이터를 포함하지 않고 인덱스 키와 데이터를 가리키는 북마크로 구성된다.