RDB 인덱스 - (1) 인덱스

이 시리즈는 RDB의 인덱스와 관련하여 다음의 개념들을 알아봅니다.

1. 인덱스
2. 다중 컬럼 인덱스
3. PK, FK, UK
4. mysql explain 인덱스 사용법

인덱스

테이블에 대한 동작의 속도를 높여주는 자료 구조
- 위키피디아

• 특정 열 값이 있는 행을 빠르게 찾는데 사용됩니다.
  • SQL 서버가 더욱 좋은 성능을 내도록 하는 전반적인 방법론을 데이터 베이스 튜닝이라고 합니다. 즉, 인덱스는 조회 작업과 관련된 데이터베이스 튜닝을 위해 쓰인다고 볼 수 있습니다.

1. 장단점

장점

• 검색속도 향상 -> 쿼리 부하 감소 -> 시스템 전체 성능 향상

단점

• 자주 반복되는 단어에 사용시 풀스캐닝보다 비효율적
  • 반복될 때마다 index를 조회하는 오버헤드 발생
• DB 크기의 약 10% 정도의 추가 공간이 필요
• 처음 인덱스 생성시 시간이 많이 소모
• 데이터 변경 작업(Insert, Update, Delete)이 자주 일어나는 경우 오히려 성능 하락

2. 인덱스의 내부 작동

B-tree 구조

• B-tree의 노드를 MySQL에선 16kB 차지하는 메모리 공간 단위 페이지라고 합니다.
• B-tree 구조를 사용하여 빠르게 SELECT문을 실행할 수 있습니다.
• CUD 작업시 페이지분할이 이루어질 수 있으며, 다수의 페이지 분할이 이루어진다면 부담스러운 작업이 될 수 있습니다.
  • 보조 인덱스는 데이터 페이지 자체가 인덱스 페이지가 아니므로 페이지 분할이 CUD 작업에서 덜 이루어져서 클러스터형보다 이러한 작업에서 유리합니다.

이외에도 해시 테이블, R-tree 구조를 사용하는 인덱스도 있다고 합니다.

해시테이블이 아닌 B-tree가 주로 사용되는 이유

결론부터 말하자면 해시는 범위 검색이 불가능하지만, B-tree는 가능하기 때문에 인덱스 생성시 주로 B-tree를 사용하는 것입니다.

해시테이블의 특성상 해시 테이블에 저장된 데이터들은 정렬되어 있지 않습니다. 따라서 >, >=, <, <=, BETWEEN과 같은 범위 검색이 불가능합니다. 반면, B-tree는 데이터가 모두 정렬되어 있기 때문에 앞서 언급한 연산자들 뿐만 아니라 (%로 시작하지 않는다는 조건에 한하여) LIKE 까지 포함한 범위 검색에서 빠르게 작업을 수행할 수 있습니다.

해시테이블이 무용지물이기만 한 것은 아닙니다. 해시 테이블은 =, <=> 연산자에 대해서는 O(1)의 시간복잡도를 가지며 매우 빠르게 처리하기 때문에, equailty 비교 연산에서는 O(logN)의 시간 복잡도를 가지는 B-tree 인덱스보다 해시 인덱스가 효율적입니다.

R-tree

N차원의 공간 데이터를 효과적으로 저장하고 지리정보와 관련된 쿼리를 빠르게 수행할 수 잇는 자료구조입니다.

예를 들어, "현재 위치에서 20km 이내의 모든 은행을 찾아라"와 같은 쿼리를 빠르게 수행합니다.

• 특징
  • 최소경계사각형(MBR: Minumum Bounding Rectangle)이라는 저장단위에 분할하여 저장합니다
  • 완전 균형 트리입니다

3. 인덱스의 종류

MySQL에서 사용되는 인덱스의 종류는 크게 클러스터형, 보조 인덱스로 나뉩니다.

클러스터형 인덱스

• 영어사전과 유사
  • 데이터를 열에 맞추어 오름차순으로 자동 정렬
    • 범위검색에서 보조형보다 유리
    • 인덱스 생성시 오랜 시간이 걸리는 단점
• 자동 생성
  • 인덱스 지정 없을 시 기본키 기반으로 클러스터형 인덱스가 자동 생성
  • UNIQUE + NOT NULL도 클러스터형 인덱스를 자동 생성
    • 단, 기본키가 없는 경우여야 하며, 기본키가 존재한다면 보조 인덱스로 생성됩니다.
• 인덱스 자체의 리프 페이지가 곧 데이터. 즉, 인덱스 자체에 데이터가 포함
  • 덕분에 조회 작업에서 보조 인덱스보다 빠릅니다.
• 하나만 존재 가능(반드시 존재할 필요는 없음)
  • 어느 열에 클러스터형 인덱스를 생성하는지에 따라서 시스템의 성능이 달라질 수 있습니다.

보조 인덱스

• 교과서 같은 책 뒤의 <찾아보기>와 유사
• 자동생성
  • UNIQUE 키마다 1개의 보조 인덱스가 자동 생성
  • 여러개 생성 가능
• 데이터 페이지는 그냥 둔 상태에서 페이지에 인덱스를 구성
• 리프 페이지는 데이터가 아닌, 데이터의 주소 값(RID, Row ID)
  • 보조 인덱스가 R에 불리하고 CUD에 유리한 이유
    • 예를 들어, INSERT 작업의 경우 데이터 페이지에서 단순히 마지막 데이터에 덧붙이기만 수행하면 됩니다.
• 여러개 존재 가능

클러스터형과 보조형 비교

한 마디로 요약하자면, R 작업은 클러스터형이, CUD 작업은 보조형이 유리합니다.

• 클러스터형이 유리한 점

  • 클러스터형은 자동정렬을 사용하여 범위 검색에서 유리합니다.
  • 데이터 페이지 자체가 인덱스 페이지로 포함되어 검색 작업에서 보조 인덱스보다 빠릅니다.

• 클러스터형이 불리한 점

  • 인덱스 생성시 자동정렬을 하므로 생성 시간이 오래 걸립니다.

• 보조형이 유리한 점

  • INSERT, DELETE, UPDATE 작업에서 페이지 분할이 덜 이루어져서 빠릅니다.

클러스터형 인덱스와 보조형 인덱스가 혼합되어 있을 경우

현실에선 PK와 UNIQUE key를 동시에 사용하는 경우가 많아서 두 종류의 인덱스가 혼용되는 경우가 많습니다.

혼합된 보조 인덱스에선 데이터의 주소 값이 아닌 클러스터 인덱스의 기본키 값을 저장합니다. 이는 클러스터 인덱스가 수정될 때마다 보조 인덱스가 가르키는 주소값이 변경되는 것을 방지하기 위함입니다.

4. 결론: 인덱스는 언제 사용해야할까?

'테이블의 데이터 구성이 어떻게 되었는지, 어떠한 조회를 많이 사용하는지' 등을 고려하여 인덱스를 사용하여야 합니다.

다음과 같은 인덱스의 특징들을 기억해두면 언제 사용할지에 대한 판단에 도움이 됩니다.

인덱스의 특징

• 열 단위로 생성
  • 한 개 혹은 두 개 이상의 열을 조합해서 인덱스를 생성할 수 있습니다.
• WHERE절에서 자주 사용되는 열
  • 테이블 조회 시에 WHERE절의 조건에 해당하는 열이 나오는 경우만 인덱스를 주로 사용합니다.
  • 가끔 쓰는 경우라면 인덱스를 만드는 것의 비용이 더 클 수 있습니다.
• 데이터의 중복도가 낮은 열
  • 성별과 같은 데이터의 종류가 작고 중복도가 높은 경우엔 만들지 않는 것이 낫습니다.
• 외래 키를 지정한 열에는 자동으로 외래 키 인덱스가 생성
  • 그리고 쿼리문에서 외래 키 인덱스가 필요할 경우 MySQL이 알아서 외래 키 인덱스를 사용합니다.
• JOIN에 자주 사용되는 열
  • 이 경우 인덱스를 생성하는게 좋습니다.
• INSERT/UPDATE/DELETE 발생 빈도
  • 인덱스는 단지 읽기에서만 성능을 향상시키므로, 데이터의 변경이 자주 이루어지는 경우라면 지양하는게 좋습니다.

부록: 문법

http://www.albumbang.com/board/board_view.jsp?board_name=free&no=141
인덱스 생성 문법은 위 링크를 참고하자

참고문헌

• 한빛 미디어 유튜브 채널
  • [이것이 MySQL이다] 09. MySQL 인덱스(1)
  • [이것이 MySQL이다] 09. MySQL 인덱스(2)
  • [이것이 MySQL이다] 09. MySQL 인덱스(3)
  • [이것이 MySQL이다] 09. MySQL 인덱스(4)
• 해시 인덱스 관련
  • stackoverflow
  • MySQL - document
  • https://enterone.tistory.com/227
• R-tree 관련
  • Wikepedia - R-tree
  • R Tree구조