[MySQL] 인덱스 구조

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

인덱스는 검색 속도를 향상할 수 있는데 여기서 말하는 검색이란 SELECT 명령에서 WHERE구로 조건을 지정하고 그에 일치하는 행을 찾는 일련의 과정을 말한다.

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

인덱스는 테이블과 별개로 독립된 데이터베이스 객체로 작성되지만, 인덱스만으로는 아무런 의미가 없어 인덱스는 테이블에 의존하는 객체라 할 수 있다.

 

 

 검색에 사용하는 알고리즘 

• 풀 테이블 스캔(full table scan)

인덱스가 지정되지 않은 테이블을 검색할 때는 풀 테이블 스캔이라 불리는 검색 방법을 사용한다.

테이블에 저장된 모든 값을 처음부터 차례로 조사해 나가는 처리방법을 사용한다.

단순 검색 방법으로, 행이 100개가 있다면 최대 100번 값을 비교하는 방식이다.

 

• 이진 탐색(binary search)

차례로 나열된 집합에 대해 유효한 검색 방법이다.

처음부터 순서대로 조사하는 것이 아니고 집합을 반으로 나누어 조사하는 검색 방법이다.

아래의 집합에서 30을 찾고자 했을 때 풀 테이블 스캔으로 찾으려면 10번 만에 찾을 수 있는 것을 이진 탐색으로 찾게 되면 3번 만에 찾을 수 있다.

이렇듯 이진 탐색은 고속으로 검색할 수 있는 탐색방법이지만 데이터가 미리 정렬되어 있어야 사용이 가능하다.

 

• 이진트리(binary tree)

대표적인 검색 알고리즘으로 탐색 방법이라기 보단 데이터 구조에 가까우며 이진 탐색에서 검색하기 쉬운 구조로 한 것이 이진트리이다.

일반적으로 테이블에 인덱스를 작성하면 테이블 데이터와 별개로 인덱스용 데이터가 저장장치에 만들어진다. 

이때 이진트리라는 데이터 구조로 작성되는데 이진트리 구조는 다음과 같다.

 

트리는 노드(node)라는 요소로 구성되는데 각 노드는 두 개의 가지로 나뉜다.

노드의 왼쪽 가지는 작은 값으로, 오른쪽 가지는 큰 값으로 나뉘는데, 이렇게 두 개의 가지로 분기하는 구조라서 '이진트리'리 불린다.

검색은 이진트리의 가지를 더듬어가며 행해진다. 

이진 탐색에서는 가운데에서부터 시작했지만, 이진트리의 경우는 트리의 맨 위에 있는 루트 노드부터 시작한다.

검색의 진행 방법은 이진 탐색과 비슷하다. 원하는 수치와 비교해서 더 크면 오른쪽 가지를, 작으면 왼쪽 가지를 조사해 나간다.

이진 탐색의 경우는 오른쪽의 가운데, 왼쪽의 가운데 값을 계산해야 하지만, 이진트리에서는 구조 자체가 검색하기 쉬우므로 가지를 따라 이동하기만 하면 된다.

이진트리에서는 집합 내에 중복하는 값을 가질 수 없는데, 같은 값을 허용하기 위해서는 '같은'이라는 제3의 가지를 가질 필요가 있다.

하지만, 이진트리에서 '같은 값을 가지는 노드를 여러 개 만들 수 없다'라는 특성은 키에 대해 유일성을 가지게 할 경우에만 유용하다.