인덱스

인덱스를 알아보기에 앞서, 랜덤 I/O와 순차 I/O에 대해 살펴보자.

 

랜덤 I/O

하드 디스크 드라이브의 플래터(원판)를 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 수 데이터를 읽는 것을 의미한다. 데이터를 R/W하기 위해 페이지의 수 만큼 시스템 콜을 요청하며, 그 횟수만큼 디스크의 헤더 이동이 발생하게 된다.

인덱스 레인지 스캔에 해당한다.

 

순차 I/O

한 번의 시스템 콜을 통해 여러 페이지 데이터를 R/W한다. 디스크의 헤더 이동이 줄어들어 랜덤 I/O에 비해 더 빠르다.

 

일반적으로 쿼리를 튜닝하는 것은 랜덤 I/O 자체를 줄이는 게 목적이며, 이 의미는 쿼리를 처리하는 데 꼭 필요한 데이터만 읽도록 쿼리를 개선하는 것을 의미한다. 풀 테이블 스캔에 해당한다.

 

---

1. 인덱스의 구분

인덱스는 데이터를 관리하는 방식(알고리즘)과 중복 값의 허용 여부에 따라 여러 가지로 나눠볼 수 있다. 가장 많이 사용되는 B-Tree 인덱스를 배우기에 앞서, 인덱스를 다양한 기준으로 나눠보자.

 

역할별

• 프라이머리 키(Primary key)
• 보조 키(세컨더리 인덱스, Secondary key)

 

데이터 저장 방식(알고리즘)

• B-Tree 인덱스 : 칼럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘
• Hash 인덱스
• Fractal-Tree 인덱스
• Merge-Tree 인덱스

 

중복 허용 여부

• 유니크(Unique) Index
• 유니크하지 않은(Non-Unique) Index

 

기능별

• 전문(Full Text) 검색용 인덱스
• 공간 검색용 인덱스 : R-Tree

 

---

2. B-Tree 인덱스

B-Tree 인덱스는 트리 구조의 최상위에 하나의 루트 노드가 존재하고 하위에 자식 노드가 붙어 있는 형태이다. 트리 구조의 가장 하위에 있는 노드를 "리프 노드"라고 하고, 루트도 리프도 아닌 중간 노드를 "브랜치 노드"라고 한다. 

데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다.

 

 

 

// 추가 예정

일반적인 B-Tree 구조

 

MyISAM에서의 B-Tree 구조

 

InnoDB에서의 B-Tree 구조

 

 

 

---

3. B-Tree 인덱스 키 추가 및 삭제

 

1) 인덱스 키 추가

• 새로운 키 값이 B-Tree에 저장될 때 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있다.
  • 리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리(Split)되어야 하는데, 이는 상위 브랜치, 루트 노드까지 처리 범위가 넓어질 수 있다.
• MyISAM이나 MEMORY 엔진의 경우 INSERT 실행 시 즉시 새로운 키 값을 B-Tree 인덱스에 변경한다.
• InnoDB 엔진은 필요 시 체인지 버퍼를 통해 인덱스 키 추가 작업을 지연시켜 나중에 처리할 수 있다. 
  -> 하지만 프라이머리 키나 유니크 인덱스의 경우 중복 체크가 필요하기 때문에 즉시 B-Tree에 반영한다.

 

2) 인덱스 키 삭제

• 해당 키 값이 저장된 B-Tree의 리프 노드를 찾아 삭제 마킹을 수행한다. 이 공간은 재활용할 수 있다.
• InnoDB에서 역시 해당 공간을 버퍼링해 지연 처리할 수 있다.

 

3) 인덱스 키 변경

• 인덱스의 키 값은 그 값에 따라 저장될 리프 노드의 위치가 결정된다. 따라서 단순히 인덱스 상의 키 값만 변경하는 건 불가능하다.
• 따라서 키 값을 삭제 후 다시 새로운 키 값을 추가하는 형태로 처리된다.
• InnoDB에서는 이 작업 모두 버퍼링해 지연 처리할 수 있다.

4) 인덱스 키 검색

• 앞서 INSERT, UPDATE, DELETE 작업 시 추가 비용을 감당한 이유가 빠른 검색을 위해서이다.
• 인덱스를 검색하는 작업은 B-Tree의 루트 노드부터 시작해 최종 리프 노드까지 이동하면서 비교 작업을 수행하는데, 이 과정을 "트리 탐색"이라고 한다.

 

---

4. 클러스터링 인덱스

• MySQL에서 InnoDB 스토리지 엔진에서 클러스터링 인덱스를 지원한다.
• PK 값이 비슷한 레코드끼리 묶어서 저장한다.
• 일반적으로 InnoDB와 같이 클러스터링 인덱스로 저장되는 테이블은 PK 기반 검색이 매우 빠르다. 하지만 레코드의 저장, PK의 변경은 느리다.
• 일반적으로 웹 서비스와 같은 온라인 트랜잭션 환경(On-Line Transaction Processing)에서는 쓰기와 읽기의 비율이 2:8 또는 1:9 정도이므로 느린 쓰기를 감수하고 읽기를 빠르게 유지하는 것이 더 중요하다!

 

(InnoDB 기준)클러스터링 인덱스가 있을 경우, 보조 인덱스에 미치는 영향은 다음과 같다.

• InnoDB 테이블의 모든 보조 인덱스는 PK 키 값을 저장하도록 되어있다.
• 따라서 클러스터링 인덱스를 사용하지 않는 스토리지 엔진보다 한 단계 더 인덱스를 탄다고 이해하면 된다. 

 

장점

• PK 검색 시 처리 성능이 매우 빠르다.
• 테이블의 모든 보조 인덱스가 PK를 가지고 있으므로 인덱스만으로 처리될 수 있는 경우가 많다. == 커버링 인덱스

 

단점

• 테이블의 모든 보조 인덱스가 클러스터 키를 갖기 때문에 클러스터 키의 크기에 비례하여 전체 인덱스 크기도 커지게 된다.
• INSERT 시 PK에 의해 레코드의 저장 위치가 결정되므로 처리 성능이 느리다.
• PK 변경 시 레코드를 DELETE, INSERT 하는 작업이 필요해서 처리 성능이 느리다.

 

---

5. 유니크 인덱스

• 유니크 인덱스는 제약 조건에 가깝다. 말 그대로 인덱스에 같은 값이 2개 이상 저장될 수 없음을 의미한다.
• 유니크 인덱스에서 NULL도 저장될 수 있는데 이는 특정 값이 아니므로 2개 이상 저장될 수 있다.(PK는 NULL 허용 x) 

 

유니크 인덱스 vs 보조 인덱스

• 많은 경우 유니크 인덱스의 읽기가 더 빠르다고 생각하지만 그건 사실이 아니다. 둘을 비교하자면 보조 인덱스의 경우 디스크 읽기가 추가로 발생하는게 아닌, 중복되는 인덱스로부터 일치하는 레코드를 찾기 위해 CPU에서 컬럼값을 비교하는 작업이기 때문에 성능 상 영향이 거의 없다고 볼 수 있다.
• 유니크 인덱스의 경우 중복된 값을 체크하는 과정이 항상 필요하며 이로 인해 데드락이 빈번하게 발생한다.
• InnoDB에서는 인덱스 키의 저장을 버퍼링 하기 위한 버퍼(인서트 버퍼)가 사용되는데, 유니크 인덱스는 중복 체크 과정으로 인해 작업을 버퍼링할 수 없다. 따라서 유니크 인덱스는 일반 세컨더리 인덱스보다 처리가 더 느리다.
• 유일성이 보장되어야 할 경우가 아니라면, 보조 인덱스를 고려하자.

 

---

6. 외래키

외래 키 제약이 설정되면 자동으로 연관되는 테이블의 컬럼에 인덱스가 생성된다. 외래키가 제거되지 않은 상태에서는 자동으로 생성된 인덱스를 삭제할 수 없다.

 

중요한 특징은 다음과 같다.

• 테이블의 변경(쓰기 잠금)이 발생하는 경우에만 잠금 경합(잠금 대기)이 발생한다.
  -> 자식 테이블의 외래키를 변경할 경우, 해당하는 부모 테이블의 레코드가 쓰기 잠금이 걸려있는 경우에만 대기가 발생한다.
  -> 자식 테이블의 외래키가 아닌 컬럼의 변경은 잠금이 발생하지 않는다.
• 외래키와 연관되지 않은 컬럼의 변경은 최대한 잠금 경합(잠금 대기)을 발생시키지 않는다.