데이터베이스 첫걸음 정리 - 28장. 인덱스 구조

인덱스

인덱스는 테이블에 붙여진 색인으로, 역할은 검색속도의 향상입니다.

 

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

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

 

인덱스의 경우 책의 목차나 색인과 비슷합니다.

책 안에 있는 특정한 부분을 찾고 싶은 경우 본문을 처음부터 읽는 것 보다 목차나 색인을 참고해서 찾는 편이 효율적일 것입니다. 바로 인덱스가 이런 역할을 합니다.

인덱스의 구조도 목차나 색인과 비슷합니다. 목차나 색인에 제목/키워드별 페이지 번호가 적혀있듯, 데이터베이스 인덱스에는 검색 시에 쓰이는 키워드와 대응하는 데이터 행의 장소가 저장되어 있습니다.

인덱스는 테이블과는 별개로 독립된 데이터베이스 객체로 작성됩니다.

하지만 인덱스만으로는 아무런 의미가 없습니다. 목차밖에 없는 책은 본 적이 없는 것 처럼, 인덱스는 테이블에 의존하는 객체라 할 수 있습니다.

대부분의 데이터베이스에서는 테이블을 삭제하면 인덱스도 같이 삭제됩니다.

검색에 사용하는 알고리즘

인덱스를 사용하면 효율적으로 검색할 수 있는 이유는 무엇일까요?

대량의 데이터를 효율적으로 검색하는 방법에 관해서 여러 가지로 연구되어 왔으며 이를 위해 다양한 데이터 탐색이라든가 검색 알고리즘이 등장했습니다.

인덱스는 이를 적용하여 효율적인 검색을 할 수 있도록 했습니다.

데이터베이스 인덱스에 쓰이는 대표적인 알고리즘으로는 “이진트리(binary tree)”가 있으며, 그 다음으로 “해시"가 유명합니다.

풀 테이블 스캔(full table scan)

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

풀 테이블 스캔은 테이블에 저장된 모든 값을 처음부터 차례로 조사해나가는 것입니다.

아주 단순한 검색방법으로, 행이 1000건 있다면 최대 1000번 값을 비교합니다.

이진 탐색(binary search)

이진 탐색은 정렬되어 있는 집합에 대해 유효한 검색 방법입니다.

처음부터 순서대로 찾는 것이 아닌 집합을 반으로 나누어 찾는 검색방법입니다.

예를 들어 다음과 같은 그림이 있다고 가정해봅시다.

위의 그림에서 30인 값을 찾고 싶은 경우 먼저 집합을 반으로 나눈 후 가운데 부터 값을 찾습니다.

여기서 가운데 값은 10입니다.

지금 검색하려는 값인 30이 현재 값인 10보다 크기 때문에 찾고 있는 값이 오른쪽에 있는 것을 알 수 있습니다.

이번에는 오른쪽의 가운데 값인 32를 기준으로 잡아서 찾습니다.

가운데 값인 32가 찾는 값인 30보다 크므로 값은 왼쪽에 있다는 것을 알 수 있습니다.

이 경우 3번만에 30을 찾을 것을 알 수 있습니다.

 

만약, 풀 테이블 스캔을 사용했다면 6번을 비교했어야 하지만 이진 탐색을 사용함으로써 더 빨리 값을 찾을 수 있게 되었습니다.

물론 지금과 같이 데이터 수가 얼마 없다면 속도 차이가 크게 없을 수 있지만 데이터베이스의 데이터 수가 늘어날 수 록 이 차이는 유의미하게 늘어납니다.

풀 테이블 스캔을 한다면 데이터 수의 비례해 비교횟수가 늘어나지만 그에 비해 이진 탐색은 데이터 수가 배가 되어도 비교 회수는 1회 밖에 늘어나지 않습니다.

이런 점에서 평균적으로 이진 탐색이 더 빠르게 데이터를 검색할 수 있다는 것을 알 수 있습니다.

이진 트리

이진 탐색은 고속으로 검색할 수 있는 탐색 방법이지만 데이터가 미리 정렬되어 있어야 합니다.

하지만 테이블 내의 행을 언제나 정렬된 상태로 두는 것은 힘든 작업입니다.

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

이때 이진 트리라는 데이터 구조로 작성됩니다.

다음은 이진 트리 예시입니다.

트리는 노드라는 요소로 구성됩니다.

각 노드는 최대 두개의 가지로 나뉩니다. 노드의 왼쪽 가지는 작은 값으로, 오른쪽 가지는 큰 값으로 나뉘어져 있습니다.

 

두 개의 가지로 분기하는 구조라서 “이진 트리”로 불리게 됩니다.

이번에는 이진 트리의 사용법을 알아보기 위해 10이라는 값을 한번 찾아봅시다.

이진 탐색에서는 가운데 값 부터 검색하기 시작했습니다. 하지만 이진트리의 경우에는 트리의 루트 노드부터 검색을 시작합니다.

검색의 진행 방식은 이진 탐색과 마찬가지로 원하는 수치와 비교해서 더 작으면 왼쪽으로 더 크면 오른쪽으로 이동합니다.

현재 찾는 값이 10이므로 20보다 작기때문에 왼쪽으로 이동합니다.

현재 이동한 값인 5보다 찾는 값인 10이 더크기 때문에 오른쪽으로 이동합니다.

위와 같이 10이라는 값에 도달하게 되었습니다.

이진 트리라는 데이터 구조를 사용하면 정렬 상태가 유지되기 때문에 바로 이진 탐색을 사용할 수 있게 됩니다.

유일성

이진 트리의 구조를 살피다 보면, 같은 값을 가지는 노드가 여러 개 있을 때 결과에 대한 의문이 생길 수 있습니다.

사실 이진 트리에서는 집합 내에 중복하는 값을 가질 수 없습니다.

즉, 노드의 가지는 큰 쪽과 작은쪽의 두가지로 나뉘며 같은 값을 허용하기 위해서는 “같은"이라는 제 3의 가지를 가질 필요가 있습니다.

이때문에 이진 트리를 사용하는 경우 “같은 값을 가지는 노드를 여러 개 만들 수 없다"라는 특성때문에 키에 대하여 유일성을 가지게 할 경우에만 유용합니다.

그래서 기본키 제약은 이진 트리로 인덱스를 작성하는 데이터베이스가 많습니다.

정리

• 인덱스는 테이블에 붙여진 색인으로, 역할은 검색속도의 향상입니다.
• 인덱스는 테이블과는 별개로 독립된 데이터베이스 객체로 작성되지만 테이블이 존재하지 않는 인덱스는 의미가 없으므로 대부분의 데이터베이스는 테이블이 삭제될 때 인덱스도 같이 삭제 됩니다.
• 데이터베이스 인덱스에 쓰이는 대표적인 알고리즘으로는 이진트리(binary tree)가 있습니다.
• 인덱스가 지정되지 않는 테이블을 검색할 때는 풀 테이블 스캔이라는 검색 방법을 사용하며, 풀 테이블 스캔은 테이블에 저장된 모든 값을 처음부터 차례로 검색하는 방식입니다.
• 이진 탐색은 정렬되어 있는 집합에 대해 유효한검색 방법으로, 처음부터 순서대로 찾는 것이 아닌 집합을 반으로 나누어 찾는 검색방법입니다.
• 이진 트리는 노드라는 요소로 구성되며, 각 노드는 최대 두개의 가지로 나뉘어 노드의 왼쪽 가지는 작은 값으로, 오른쪽 가지는 큰 값으로 나뉘어져 있습니다.
• 이진 트리의 경우 같은 값을 가지는 노드를 여러개 만들 수 없기 때문에 인덱스로 설정한 값은 유일성을 가져야 합니다.