[DB] 인덱스

DBMS는 사용자가 만든 테이블을 저장 장치에 저장하고 필요에 따라 검색하여 결과를 보여준다. 그렇다면 DBMS는 데이터를 어떻게 저장하고 검색할까? 이 절에서는 DBMS에서 테이블이 저장되는 물리적인 구조와 함께 대부분의 관계 모델 데이터베이스가 사용하는 인덱스의 기본구조인 B-tree에 대해 알아보자.

 

데이터베이스의 물리적 저장

 

우리가 데이블을 생성하고 테이블에 데이터를 저장할 때 DBMS는 데이터를 어디에 어떻게 저장할까? 질문을 바꿔 워드프로세서로 작성한 문서를 어떻게 저장될까? 대부분 첫 번째 질문에 대해서는 선뜻 답하기 어려워도 두 번째 질문에는 쉽게 답할 수 있을 것이다. 워드프로세서로 작성한 문서는 파일 형태로 저장된다. 이 문서 파일은 워드프로세서만의 구조로 이루어져 있다. DBMS 역시 데이터를 DBMS만의 고유한 방식으로 저장하여 관리한다. 이러한 자료는 보조기억장치인 HDD, SSD에 저장된다.

 

 

보조기억장치에 저장되는 DBMS의 연산속도는 근본적으로 느리다. 때문에 이러한 속도 문제를 해결하기 위해 주기억장치에 DBMS가 사용하는 공간 중 일부를 버퍼 풀로 만들어 사용하는 방법이 있다. DB에 자주 사용하는 데이터를 저장해 두며 LRU 알고리즘을 이용하여 사용빈도가 높은 데이터 위주로 저장되고 관리한다.

 

LRU란

기억장소를 관리하는 알고리즘으로 최근에 사용되지 않은 순서대로 기억 장소에서 할당을 제외하는 방법이다.

 

인덱스와 B-tree

 

인덱스랑 자료를 쉬고 빠르게 찾을 수 있도록 만든 데이터 구조이다. 도서관에서 책을 찾을 때 서지목록을 보고 책의 위치를 찾는 것처럼 인덱스도 같은 역할을 한다. 데이터베이스에서 인덱스란 원하는 데이터를 빨리 찾기 위해 튜플의 키 값에 대한 물리적 위치를 기록해 둔 자료구조이다. 일반적인 RDBMS의 인덱스는 대부분 B-tree 구조로 되어 있다. 여기에서는 먼저 B-tree의 기본 구조를 알아보고 실제 인덱스 구조에 대해 살펴본다.

 

B-tree 구조

 

B-tree의 각 노드는 키 값과 포인터를 가진다. 키 값은 오름차순으로 저장되어 있으며, 키 값 좌우에 있는 포인터는 각각 키 값보다 작은 값과 큰 값을 가진 다음 노드를 가리킨다. 따라서 키 값을 비교하여 다음 단계의 노드를 쉽게 찾을 수 있다. 트리의 가장 상위 노드를 루트 노드라고 한다. 모든 검색은 루트 노드에서부터 시작하여 내부 노드를 지나 리프 노드까지 내려가면서 이루어진다. B-tree는 키 값이 새로 추가되거나 삭제될 경우 동적으로 노드를 분할하거나 통합하여 항상 균형 상태를 유지한다.

 

B-tree 예시

 

B-tree에서 7을 찾는다고 가정

1. 루트 노드에서는 7이 4보다 크기 때문에 오른쪽으로 이동한다.
2. 내부 노드에서는 7이 6보다 크기 때문에 오른쪽으로 이동한다.
3. 리프 노드에서 7을 발견한다.

B-tree에서 검색은 루트 노드에서부터 값을 비교해 중간 단계 내부 노드에서 해당 노드를 찾고 마지막 레벨인 리프 노드에서 해당 데이터의 저장 위치를 찾아 찾고자 하는 행을 바로 찾을 수 있다.

 

인덱스의 특징

• 인덱스는 테이블에서 한 개 이상의 속성을 이용하여 생성한다.
• 빠른 검색과 함께 효율적인 레코드 접근이 가능하다.
• 순서대로 정렬된 속성과 데이터의 위치만 보유하므로 테이블보다 작은 공간을 차지한다.
• 저장된 값들은 테이블의 부분집합이 된다.
• 일반적으로 B-tree 형태의 구조를 가진다.
• 데이터의 수정, 삭제 등의 변경이 발생하면 인덱스의 재구성이 필요하다.

 

MySQL 인덱스

 

MySQL의 인덱스는 2개로 클러스터 인덱스와 보조 인덱스로 나누어지며 모두 B-tree 인덱스를 기본으로 한다.

 

클러스터 인덱스

클러스터 인덱스는 인덱스의 리프 노드들이 정렬된 상태로 저장된 테이블 자체가 된다. 예를 들어 도서번호 8번을 찾을 경우 루트 노드의 키 8을 비교해서 3번째 행의 7보다 크고 4번째 행의 10보다 작다는 것을 발견하고 이에 따라 페이지 3으로 이동하여 1행부터 순서대로 데이터를 찾는다.

 

 

 

EX) 도서번호 5번을 찾는 법

루트 노드에서 노드 키 4보다는 크고 7보다는 작다는 것을 알 수 있다.

페이지 2로 이동하여 도서번호 5번을 찾을 수 있다.

 

이러한 클러스터 인덱스는 테이블 당 하나만 생성할 수 있으며, 키 값에 의한 동등 및 범위 검색에 유리하다. 또한 테이블의 데이터가 키 값에 따라 정렬된 상태로 저장되어 특정 값을 쉽게 찾을 수 있다. 

 

보조 인덱스

DB를 사용하다 보면 테이블 데이터가 갱신 또는 삭제가 되며 여러 가지 데이터가 무작위로 저장되게 된다. 이렇게 저장된 데이터는 양이 얼마 없다면 찾는데 얼마 걸리지 않지만 데이터의 규모가 큰 경우 자료를 찾는데 오랜 시간이 들 것이다. 도서번호 8번을 찾는 경우 루트 노드를 통해 리프 노드의 두 번째 페이지를 찾아 간 후 찾고자 하는 값인 8의 row_id가 3-1을 확인한다. 해당 값은 3번째 블록의 첫 번째 행에 있어 테이블의 3번째 블록에 접근해 원하는 데이터를 가져올 수 있다. 클러스터 인덱스와는 다르게 보조 인덱스의 경우 테이블당 여러 개를 만들 수 있다. 테이블의 컬럼 하나만을 대상으로 단일 컬럼 인덱스뿐만 아니라 여러 개의 컬럼을 복합적으로 결합하여 사용하는 인덱스도 만들 수 있다.

 

 

 

MySQL 인덱스

두 개의 인덱스는 보통 같이 사용된다 Book 테이블에서 bookId를 클러스터 인덱스로, bookname을 보조 인덱스로 사용하여 bookId와 bookname 모두 빠른 검색을 필요한 경우를 보자 MySQL은 bookId를 검색할 경우 클러스터 인덱스를 이용하고, bookname을 검색할 경우 보조 인덱스를 이용하여 bookId를 찾은 다음 다시 bookId에 대한 클러스터 인덱스를 사용한다. 이렇게 하는 이유는 클러스터 인덱스로 저장된 데이터의 순서를 가능한 유지 하면서 데이터의 삽입과 삭제에 대한 인덱스 관리 비용을 줄이기 위해서다.

 

인덱스의 생성

 

인덱스는 데이터 검색을 빨리하기 위해 사용된다. 하지만 인덱스를 생성했다고 해서 데이터의 검색이 무조건 빨라지는 것은 아니다. 데이터의 양이 별로 없거나 데이터 값이 몇 종류 안 되서 선택도가 높을 경우 인덱스가 없는 게 더 빠를 수 있다.

 

선택도란 다른 값의 개수를 말하며 예를 들면 100개의 행을 가진 테이블 값이 남자/여자로 만 이루어진 두 가지라면 선택도가 높다고 할 수 있다.

 

이와 같이 의미 없이 인덱스를 생성하면 검색이 오히려 더 느려지고 공간낭비도 하게 된다. 따라서 아래의 조건을 인덱스 생성전에 생각해 보자

 

• 인덱스는 WHERE 절에 자주 사용되는 속성이어야 한다.
• 인덱스는 조인에 자주 사용되는 속성이어야 한다.
• 단일 테이블에 인덱스가 많으면 속도가 느려질 수 있다.
• 속성이 가공되는 경우 사용하지 않는다.
• 속성의 선택도가 낮을 때 유리하다. (속성 값이 모두 다른 경우)