[MySQL] 인덱스

기존의 Real MySQL (5.0, 5.1 버전) 책을 너무 유익하게 봤는데, Real MySQL 8.0이 전면 개정판이 나와서... 설레는 마음에 보면서 개인적인 공부용으로 정리하고 있습니다.
역시 믿고 보는 Real MySQL... 👍 한번 사서 보시는 것을 강력 추천드립니다!

인덱스

---

인덱스란?

DBMS에서 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져오려면 시간이 오래 걸린다.

그래서 칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 삼아 인덱스를 만들어 두는 것이다

인덱스의 효과

DBMS의 인덱스는 칼럼의 값을 주어진 순서로 미리 정렬해서 보관한다.

• 프로그래밍 언어의 자료구조로 비교하면 데이터 파일: ArrayList, 인덱스: SortedList라고 할 수 있다.
• SortedList 자료구조는 데이터가 저장될 떄마다 항상 값을 정렬해야 하므로 저장하는 과정이 복잡하고 느리지만, 이미 정렬돼 있어서 아주 빨리 원하는 값을 찾아올 수 있다.
• 이처럼 인덱스란 색인으로, INSERT, UPDATE, DELETE의 데이터 저장 성능을 희생하고 데이터의 읽기 속도를 높이는 기능이다.

인덱스의 분류

프라이머리 키

• 레코드를 대표하는 칼럼의 값으로 만들어진 인덱스
• NULL 값을 허용하지 않으며 중복을 허용하지 않는 특징

세컨더리 키 (대체 키)

• 유니크 인덱스
• 유니크하지 않은 인덱스

인덱스 알고리즘의 종류

• 상당히 많은 알고리즘이 존재하지만 대표적으로 B-Tree 인덱스와 Hash 인덱스로 구분할 수 있다.

B-Tree 알고리즘

• 가장 일반적으로 사용되는 인덱스 알고리즘
• 칼럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱하는 알고리즘
• MySQL 서버에서는 위치 기반 검색을 지원하기 위해 R-Tree 알고리즘도 있지만, 결국 R-Tree 인덱스는 B-Tree의 응용 알고리즘으로 볼 수 있다.

Hash 인덱스 알고리즘

• 칼럼의 값으로 해시값을 계산해서 인덱싱하는 알고리즘으로, 매우 빠른 검색을 지원한다.
• 값을 변형해서 인덱싱하므로 전방(Prefix) 일치오 같이 값의 일부만 검색하거나 범위를 계산할 때는 해시 인덱스를 사용할 수 없다.
• 주로 메모리 기반의 데이터베이스에서 많이 사용한다.

B-Tree 인덱스

---

가장 범용적인 목적으로 사용되는 인덱스 알고리즘으로, B는 Binary가 아닌 Balanced를 의미한다.

구조 및 특성

• B-Tree는 트리 구조의 최상위에 하나의 루트 노드가 존재하고, 그 하위에 자식 노드가 붙어 있는 형태이다.
• 트리 구조의 가장 하위에 있는 노드를 리포 노드라 하고, 트리 구조에서 중간의 노드를 브랜치 노드라고 한다.
• 데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스는 테이블의 키 칼럼만 가지고 있으므로 나머지 칼럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 한다. 이를 위해 인덱스의 리프 노드는 데이터 파일에 저장된 레코드의 주소를 가진다.

InnoDB 인덱스

프라이머리 키가 ROWID의 역할을 한다.

• MyISAM 테이블과 다르게 InnoDB 테이블에서 세컨더리 인덱스는 프라이머리 키를 주소처럼 사용한다.
• 즉, 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한번 검색해야 한다.

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

---

인덱스 키 추가

B-Tree에 저장될 때는 저장될 키 값을 이용해 B-Tree 상의 적절한 위치를 검색해야 한다.

저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장한다.

리프 노드가 꽉 차서 더는 저장할 수 없을 때는 리프 노드가 분리돼야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어진다.

• 이러한 작업 탓에 B-Tree는 상대적으로 쓰기 작업에 비용이 많이 드는 것으로 알려졌다.
• 보통 테이블에 레코드를 추가하는 작업 비용이 1이라면, 해당 테이블의 인덱스에 키를 추가하는 작업 비용을 1.5로 예측한다.

InnoDB 스토리지 엔진 인덱스 키 추가 지연 처리

InnoDB 스토리지 엔진은 INSERT 문장이 실행되면 필요하다면 인덱스 키 추가 작업을 지연시켜 나중에 처리할 수 있다.

• 하지만 프라이머리 키나 유니크 인덱스의 경우 중복 체크가 필요하기 때문에 즉시 B-Tree에 추가하거나 삭제한다.

인덱스 키 삭제

해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료된다.

• 이렇게 삭제 마킹된 인덱스 키 공간은 계속 그대로 방치하거나 재활용할 수 있다.

인덱스 키 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하므로 이 작업 역시 디스크 I/O가 필요한 작업이다.

• MySQL 5.5이상 버전의 InnoDB 스토리지 엔진에서는 이 작업 또한 버퍼링 되어 지연 처리될 수 있다.

인덱스 키 변경

B-Tree의 키 값 변경 작업은 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리된다.

• InnoDB 스토리지 엔진을 사용하는 테이블에서는 이 작업 모두 체인지 버퍼를 활용해 지연처리 될 수 있다.

인덱스 키 검색

---

인덱스를 검색하는 작업은 B-Tree의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행한다. (트리 탐색이라고 한다)

• 인덱스 트리 탐색은 SELECT에서만 사용하는 것이 아니라 UPDATE, DELETE를 처리하기 위해 항상 레코를 먼저 검색해야 할 경우에도 사용된다.

사용 범위 / 주의사항

• B-Tree 인덱스를 이용한 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우에 사용할 수 있다.
• <, >와 같은 부등호 비교 조건에서도 인덱스를 활용할 수 있다.
• 키 값의 뒷부분만 검색하는 용도로는 인덱스를 사용할 수 없다.
• 또한 인덱스의 키 값에 변형이 가해진 후 비교되는 경우에는 절대 B-Tree의 빠른 검색 기능을 사용할 수 없다.
• InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키락(갭락)이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼 있다. 따라서 UPDATE나 DELETE 문장이 실행될 때 테이블에 적절히 사용할 수 있는 인덱스가 없으면 불필요하게 많은 레코드를 잠근다. (심지어는 테이블의 모든 레코드를 잠글 수도 있다.)

B-Tree 인덱스 사용에 영향을 미치는 요소

---

인덱스 키 값의 크기

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라고 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다.

• 또한 페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 하다.
• 인덱스도 결국은 페이지 단위로 관리되며, 루트와 브랜치, 리프 노드를 구분한 기준이 바로 페이지 단위이다

DBMS의 B-Tree는 자식 노드의 개수가 2개가 아니라 가변적인 구조다.

• MySQL 5.7 버전부터는 InnoDB 스토리지 엔진의 페이지 크기를 innodb_page_size 시스템 변수를 이용해 4KB ~ 64KB 사이의 값을 선택할 수 있지만, 기본값은 16KB이다.

인덱스 키의 크기와 성능

인덱스를 구성하는 키 값의 크기가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고, 그만큼 느려진다는 것을 의미한다.

• 하나의 레코드를 위한 인덱스 크기가 커지면 커질수록 메모리에 캐시해 둘 수 있는 레코드 수는 줄어든다. 그러면 자연히 메모리의 효율이 떨어지는 결과를 가져온다.

B-Tree 깊이

인덱스의 깊이는 상당히 중요하지만 직접 제어할 방법은 없다.

B-Tree의 깊이는 MySQL에서 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제다.

• 인덱스 키 값의 크기가 커지면 커질수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수가 적어지고, 같은 레코드 건수라 하더라고 B-Tree 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 된다.

이러한 이유들로 인덱스 키 값의 크기는 가능하면 작게 만드는 것이 좋다.

선택도 (기수성)

선택도 또는 기수성은 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미한다.

• 전체 인덱스 키 값은 100개인데, 그중에서 유니크한 값의 개수가 10개라면 기수성은 10이다.

인덱스 키 값 가운데 중복된 값이 많아지면 많아질수록 기수성은 낮아지고 동시에 선택도 또한 떨어진다.

인덱스는 선택도가 높을수록 검색 대상이 줄어들기 떄문에 그만큼 빠르게 처리된다.

인덱스에서 유니크한 값의 개수는 인덱스나 쿼리의 효율성에 큰 영향을 미친다.

읽어야 하는 레코드의 건수

인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 드는 작업이다. (약 4~5배 정도의 더 많은 비용이 드는 작업이라고 예측한다)

즉 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블을 모두 직접 읽어서 필요한 레코드만 필터링하는 방식으로 처리하는 것이 효율적이다.