[데이터베이스] 인덱스(Index)

1. Index?

위키백과는 다음과 같이 설명하고 있다.

- **인덱스는 데이터베이스 분야에 있어서 테이블에 대한 동작의 속도를 높여주는 자료구조**
- 인덱스는 테이블 내의 1개 이상의 컬럼을 이용하여 생성됨
- 고속의 검색 동작뿐만 아니라 레코드 접근과 관련 효율적인 순서 매김 동작에 대한 기초 제공
- 인덱스를 저장하는 데 필요한 디스크 공간은 보통 테이블을 저장하는 데 필요한 디스크 공간보다 작음
  (보통 인덱스는 키-필드만 갖고 있고, 테이블의 다른 세부 항목들은 갖고 있지 않기 때문)
- 관계형 데이터베이스에서는 인덱스는 테이블 부분에 대한 하나의 사본

→ 모든 레코드에서 full-scan하는 것이 아니라 색인화(특정 범위 내로 한정. 따로 파일로 저장)하여 데이터를 찾는 기술

→ 검색 연산을 실행했을 때 성능 향상을 가져다줌

2. Index 자료구조

DBMS는 다양한 알고리즘으로 index를 관리하는데 일반적으로 B-Tree에서 파생된 B+Tree 알고리즘을 사용한다.

B-Tree 알고리즘

이진 트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 밸런스를 맞추는 트리 구조. 정렬된 순서를 보장.

• 모든 노드들은 키와 자식노드에 대한 포인터로 이루어져 있음
  • 파란색 부분은 각 노드의 key(그림에는 없지만 data도 포함됨)
  • 빨간색 부분은 자식 노드들을 가리키는 포인터
• 모든 리프노드들이 같은 높이에 있음 → 균등한 응답 속도 보장(O(logN)

[자료구조] 그림으로 알아보는 B-Tree

B+Tree 알고리즘

B+Tree는 B-Tree를 개선시킨 알고리즘이다. 동작 방식은 B-Tree와 유사하지만 리프노드가 연결리스트 형태를 띄어 선형 검색이 가능하다.

• 모든 key, data가 리프노드에 모여 있음
  • B-Tree는 리프노드가 아닌 각자 key마다 data를 가졌음
• 모든 리프노드가 연결리스트 형태를 가짐
  • B-Tree는 옆에 있는 리프노드를 검사할 때 다시 루트 노드부터 검사해야함
  • B+Tree는 리프노드에서 선형 검사가 가능해짐
• 리프노드의 부모 key ≤ 리프노트 첫번째 key

[자료구조] 그림으로 알아보는 B+Tree

왜 B+Tree를 사용할까?

Hash Table을 이용하면 O(1)의 시간 복잡도로 더 빠르게 데이터에 접근이 가능할텐데 왜 B+Tree를 사용할까?

→ Hash Table은 동등 연산(=)에 특화되어 있기 때문에 SELECT 절의 조건에 부등호 연산(<, >)이 포함된 경우 문제가 발생할 수 있다.

3. Index의 구조와 작동원리

Index 구조

• Index는 논리적/물리적으로 테이블과 독립적임
  • 테이블은 컬럼에 데이터가 정렬되지 않고 순서대로 들어가지만,
  • Index는 Key-RowID 컬럼 두개로 이루어져 있고 오름차순, 내림차순으로 정렬이 가능함
    • Key : 인덱스를 생성하라고 지정한 컬럼의 값
• MySQL에서 테이블 생성시, 3가지 파일이 생성됨
  • {테이블명}.FRM : 테이블 구조가 저장되어 있는 파일
  • {테이블명}.MYD: 실제 데이터가 있는 파일
  • {테이블명}.MYI : INDEX 정보가 들어있는 파일
  → 사용자가 쿼리를 통해 Index를 사용하는 컬럼을 검색하게 되면, MYI 파일의 내용을 활용함.

Index 작동 원리

SELECT *
FROM EMP
WHERE empno=7902;

데이터 파일의 블록이 10만개 일 때, 위 SQL문을 수행시에

1. 서버 프로세스가 파싱 과정을 마친 후 DB buffer cache에 empno 가 7902인 정보가 있는지 확인한다.
2. 정보가 없으면 하드 디스크 파일에서 7902정보를 가진 블록을 복사해서 DB buffer cache로 가져온 후 7902 정보만 골라내서 사용자에게 보여줌

이 때 두 가지 경우로 나눌 수 있는데,

• Index 없는 경우 : 7902정보가 어떤 블록에 들어 있는지 모르므로 10만개 전부 db buffer cache로 복사한 후 하나하나 찾는다.
• Index 있는 경우 : where 절의 컬럼이 index가 만들어져 있는지 확인 후, 인덱스에 먼저 가서 7902정보가 어떤 ROWID를 가지고 있는지 확인한 후 해당 ROWID에 있는 블록만 찾아가서 db buffer cache에 복사함.

*(DB buffer cache에 대해서 추가로 함께 알아볼 필요성이 있음!)

4. Index 장단점

장점

• 검색과 정렬 속도를 향상시킨다.
• 그 결과 시스템의 부하가 줄어들어 시스템 전체 성능 향상에 도움이 된다.

단점

• 인덱스가 데이터베이스 공간을 차지해 추가적인 공간이 필요해진다. (DB의 10퍼센트 내외의 공간이 추가로 필요)
• 인덱스를 생성하는데 시간이 많이 소요될 수 있다.
• 인덱스는 검색에 최적화된 기능이기 때문에, 삽입, 삭제, 수정이 자주 일어날 경우에 인덱스를 재작성해야 할 필요가 있기에 성능에 영향을 끼칠 수 있다.
  • INSERT : 인덱스 추가로 인해 index split이 발생하고 이는 성능면에서 불리하다.
    • Index split : 새로운 index key가 들어왔을 때 블록 내에 저장할 영역이 없어 새로운 블록을 할당하는 것
  • DELETE : index에서 데이터가 delete 되는 경우, 데이터가 지워지지 않고 사용 안됨 표시만 해두기 때문에 공간 낭비가 생긴다.
  • UPDATE : index에는 update라는 개념이 존재하지 않는다. delete와 insert 작업이 동시에 일어나기 때문에 큰 부하를 가져온다.

Index를 만들 때 어떤 기준으로 만드는 게 좋을까?

• 크기가 큰 테이블만 만든다.
  • 크기가 작은 테이블에는 인덱스나 풀 스캔이나 큰 차이가 없음
• 기본키 제약이나 유일성 제약이 부여된 칼럼에는 불필요하다.
  • PK가 부여된 컬럼에는 자동으로 인덱스가 작성되어 있고, 유일성 제약이 붙어있는 컬럼 또한 동일함
  → 자동으로 인덱스가 작성되는 이유는 값의 중복 체크를 하려면 데이터를 정렬해야 하는데 인덱스를 작성해 정렬하는 것이 편리하기 때문
• Cardinality가 높은 컬럼에 만든다.
  • Cardinality == 값의 분산도
  • 특정 컬럼에 대해 많은 종류의 값을 가진다면 Cardinality가 높은 것. 값의 종류가 적으면 낮은 것
  • Cardinality가 낮은 컬럼에 인덱스를 적용하면 중복된 값이 많아 인덱스 트리를 따라가는데 조작이 증가함

 

[참고]

[MySQL] 인덱스(Index) 정리

[SQL] Index(인덱스)