28강 인덱스 구조

색인이라고도 불리는 인덱스는 데이터베이스 객체 중 하나이다.

인덱스

인덱스는 테이블에 붙여진 색인이라 할 수 있다. 인덱스의 역할은 검색속도의 향상이다.

여기서 검색이란 SELECT 명령에 WHERE 구로 조건을 지정하고 그에 일치하는 행을 찾는 일련의 과정을 말한다.

테이블에 인덱스가 지정되어 있으면 효율적으로 검색할 수 있으므로 WHERE로 조건이 지정된 SELECT 명령의 처리 속도가 향상된다.

인덱스의 구조도 책의 목차나 색인과 비슷하다. 데이터베이스의 인덱스에는 검색 시에 쓰이는 키워드와 대응하는 데이터 행의 장소가 저장되어 있다.

인덱스는 테이블과는 별개로 독립된 데이터베이스 객체로 작성된다. 하지만 인덱스는 테이블에 의존하는 객체이다. 대부분의 데이터베이스에서는 테이블이 삭제되면 인덱스도 같이 삭제된다.

인덱스를 사용하면 효율적으로 검색할 수 있는 이유는 인덱스의 구조가 검색에 용이한 알고리즘을 활용하고 있어서이다.

탐색 방법으로 이진 탐색(binary search)가 있다. 이진 탐색에서 검색하기 쉬운 구조로 되어 있는 것이 이진 트리이다.

이진 탐색과 이진 트리의 차이로는 데이터 구조이다. 이진 탐색으로는 고속으로 검색할 수 있는 탐색 방법이지만 데이터가 미리 정렬되어 있어야 한다. 테이블 내의 행을 언제나 정렬된 상태로 두는 것은 힘든 작업이다.

일반적으로 테이블에 인덱스를 작성하면 테이블 데이터와 별개로 인덱스용 데이터가 저장장치에 만들어지는데, 이 때 이진 트리라는 데이터 구조로 작성된다.

트리는 노드라는 요소로 구성되고, 각 노드는 두 개의 가지로 나뉜다. 노드의 왼쪽 가지는 작은 값, 오른쪽 가지는 큰 값으로 나뉘어져 있다.

이진 트리를 이용할 때, 같은 값을 가지는 노드가 여러 개 있을 때의 결과는 어떨까?

사실 이진 트리에서는 집합 내에 중복하는 값을 가질 수 없다. 즉, 노드의 가지는 큰 쪽과 작은 쪽의 두 가지로 나뉘며, 같은 값을 허용하기 위해서는 같은이라는 제 3의 가지를 가져야 한다.

하지만, 이진 트리에서 같은 값을 가지는 노드를 여러 개 만들 수 없다.라는 특성은 키에 대하여 유일성을 가지게 할 경우에만 유용하다. 그래서 이진 트리로 인덱스를 작성하는 데이터베이스가 기본키 제약을 가지게 되는 것이라고 할 수 있다.

이진 트리에는 중복하는 값을 등록할 수 없다.