인덱스란
데이터베이스 분야에 있어서 테이블에 대한 동작의 속도를 높여주는 자료 구조를 일컫는다.
RealMySQL을 기반으로 인덱스의 내용을 정리하고 동작 원리와 트레이드 오프에 대해서 알아보는 시간을 가져보겠다.
본문
인덱스의 종류
- Primary Key : 레코드 대표하는 컬럼 값으로 만들어진 인덱스를 의미한다.
물리적으로 정렬된 위치에 인덱스가 존재하는 것이 핵심이다.- NULL 값 허용 x
- 중복을 허용 x
- Secondary Key : 프라이머리 키를 제외한 나머지 인덱스는 세컨더리 인덱스로 분류한다.
- 유니크 인덱스: 유니크 인덱스로 동등 조건 검색 시 항상 1건의 레코드만 검색하면 더 찾지 않아도 된다는 것을 옵티마이저에게 알려주는 효과가 난다.
- 유니크하지 않은 인덱스
B-Tree 인덱스
B-TREE 구조
- B-Tree 구조는 최상위에 하나의 루트 노드가 존재하고 그 하위에 자식노드가 붙어 있는 형태다.
- 트리 구조의 가장 하위노드를 리프노드라 하고, 트리 구조에서 루트노드와, 리프노드도 아닌 중간 노드를 브랜치 노드라고 한다.
- 데이터베이스에서 인덱스와 실제 데이터가 저장된 데이터는 따로 관리되는데, 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있다.
인덱스 키 값은 모두 정렬돼 있지만, 데이터 파일 레코드는 임의의 순서로 저장되어있다. 데이터 파일의 레코드가 삭제되어 빈공간이 생기면 다음 INSERT는 가능한 삭제 공간을 재활용하도록 DBMS가 설계되기 때문에 항상 INSERT 된 순서로 저장되는 것은 아니다.
세컨더리 인덱스의 경우 - MyISAM 테이블은 세컨더리 인덱스가 물리적인 주소를 가진다. - InnoDB 테이블은 프라이머리 키를 주소처럼 사용하기 때문에 논리적인 주소를 가진다
기본적으로 테이블에서 인덱스를 통해 레코드를 읽을 때는 데이터 파일을 바로 찾아가지 않고, 인덱스를 한 번 거친 후 프라이머리 키 인덱스의 리프 페이지에 저장돼 있는 레코드를 읽는다.
B-Tree 인덱스 키 추가 및 삭제
인덱스 추가
새로운 키 값이 B-Tree 저장될 때 테이블의 스토리지 엔진에 따라 새로운 키값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있다.
B-Tree 저장될 때는 저장될 키 값을 이용해 B-Tree 상의 적절한 위치를 검색해야 한다. 저장될 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree 의 리프 노드에 저장한다.
대략적으로 계산하면 인덱스 추가 작업 비용을 1.5 정도로 예측 작업 비용을 1이라 가정시, 테이블의 작업 비용은 1이고 3개인경우에는 5.5 정도의 비용을 예측한다.
이 비용의 대부분이 메모리와 CPU에서 처리하는 시간이 아니라 디스크로부터 인덱스 페이지를 읽고 쓰기를 해야 해서 걸리는 시간이다.
- InnoDB를 제외한 스토리지 엔진을 사용하는 테이블에서는 INSERT 문장이 실행되면 즉시 새로운 키 값을 B-Tree 인덱스에 변경한다.
- InnoDB는 인덱스 키추가 작업을 지연시켜 나중에 처리할 수 있다.
프라이머리 키나 유니크 인덱스의 경우 중복 체크가 필요하기 때문에 즉시 B-Tree에서 삭제하거나 추가한다.
인덱스 삭제
B-Tree 의 키값이 삭제되는 경우는 간단하다. 해당 키값이 저장된 B-Tree의 리프노드를 찾아서 그냥 삭제마크만 하면 작업이 완료된다. 삭제 마킹된 인덱스 키 공간은 그대로 방치하거나 재활용 가능하다.
인덱스 키 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하므로 이 작업 역시 디스크 I/O가 필요한 작업이다.
MySQL 5.5 이상 버전의 InnoDB 스토리지 엔진에서는 이 작업 또한 버퍼링 되어 지연처리 될 수 있다. 처리가 지연된 인덱스 키 삭제는 MySQL 서버가 내부적으로 처리하므로 걱정할 필요가 없다.
인덱스 키 변경
인덱스의 키 값은 그 값에 따라 저장될 리프 노드의 위치가 결정되므로 B-Tree의 키 값이 변경되는 경우에는 단순히 인덱스 상의 키 값만 변경하는 것은 불가능하다.
따라서 인덱스 키 값 변경은 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리한다.
InnoDB 스토리지 엔진을 사용하는 테이블에 대해서는 이 작업 모두 체인지 버퍼를 활용해 지연 처리 가능하다.
인덱스 키 검색
인덱스 트리 검색 작업은 B-Tree 의 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행한다. 이 과정을 트리 탐색이라고 한다.
- 트리 탐색은 Select, Update, Delete 처리 위해 항상 해당 레코드를 먼저 검색해야 할 경우 사용한다.
- B-Tree 인덱스 이용 검색은 100% 일치 또는 값의 앞부분만 일치하는 경우에만 사용 가능
- 부등호 비교 조건에서도 활용 가능
- 인덱스 키 값에 변형이 가해진 후 비교되는 경우에는 절대 B-Tree 의 빠른 검색 기능 활용이 불가능
InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키 락은 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼 있다. 따라서 UPDATE나 DELETE 문장이 실행될 때 적절한 인덱스가 없으면 불필요하게 많은 레코드를 잠근다.
B-Tree 인덱스 사용에 영향 미치는 요소
칼럼의 크기와 레코드 건수, 그리고 유니크한 인덱스 키 값의 개수에 의해 영향 받을 수 있다.
인덱스 키 값의 크기
InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라고 하며, 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 된다.
페이지는 InnoDB 스토리지 엔진의 버퍼 풀에서 데이터를 버퍼링 하는 기본 단위이기도 하다. 인덱스도 결국 페이지 단위로 관리되며, 루트와 브랜치, 리프 노드를 구분한 기준이 바로 페이지 단위이다.
MySQL 의 B-Tree 는 자식 노드를 인덱스의 페이지 크기와 키 값의 크기에 따라 결정한다.
InnoDB 페이지의 크기는 시스템 변수를 사용해 선택할 수 있지만 기본 값은 16KB이다.
인덱스 구성하는 키 값의 크기가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고, 그만큼 느려진다는 것을 의미한다.
인덱스의 키값의 길이가 길어진다는 것은 전체적으로 인덱스의 크기가 커진다는 것을 의미한다. 하지만 인덱스를 캐시해두는 InnoDB 버퍼 풀이나 MyISAM 의 키 캐시 영역은 크기가 제한적이기 때문에 하나의 레코드를 위한 인덱스의 크기가 커지면 커질수록 메모리에 캐시해 둘 수 있는 레코드의 수는 줄어든다.
B-Tree 깊이
B-Tree 인덱스의 깊이는 상당히 중요하지만 제어할 방법은 없다.
인덱스 키값의 평균 크기가 늘어나면 B-Tree 의 깊이가 깊어진다.
B-Tree 의 깊이는 MySQL에서 값을 검색할 때 몇번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제다. 결론적으로 인덱스 키값의 크기가 커지면 커질수록 인덱스 페이지에 담을 수 있는 키 값 개수가 적어지고, 같은 레코드 건수라 하더라도 B-Tree 의 깊이가 깊어져서 디스크 읽기가 더많이 필요해진다.
선택도
인덱스 키값 가운데 유니크한 값의 수를 의미한다. 인덱스 키 값 가운데 중복된 값이 많아지면 많아질수록 기수성은 낮아지고 동시에 선택도 또한 떨어진다. 인덱스는 선택도가 높을수록 검색 대상이 줄어들기 때문에 그만큼 빠르게 처리된다.
읽어야하는 레코드 건수
인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 테이블의 레코드를 읽는 것보다 높은 비용이 드는 작업이다.
DBMS의 옵티마이저에서 인덱스를 통해 레코드 1건을 읽는 것은 직접 레코드 1건을 읽는 것보다 4~5배 정도 비용이 더 많이 드는 작업인 것으로 예측한다.
인덱스를 통해 읽어야할 레코드 건수가 전체 테이블 레코드의 20~25 %를 넘어서면 인덱스를 이용하지 않고 테이블을 모두 직접 읽어서 필요한 레코드만 가려내는 방식으로 처리하는 것이 효율적이다.
인덱스의 효율을 얻을 수 없는 경우 MySQL의 옵티 마이저가 기본적으로 힌트 무시후 테이블 직접 읽는 방식으로 처리하겠지만 기본으로 알고 있어야한다.
클러스터링 인덱스
테이블의 프라이머리 키에만 적용되는 내용이다. 프라이머리 키값이 비슷한 레코드 끼리 묶어서 저장하는 것을 클러스터링 인덱스라고 표현한다. 프라이머리 키 값에 의해 레코드의 저장 위치가 결정된다는 것이다. 프라이머리 키값이 변경된다면 물리적 저장 위치가 바뀌어야한다. 테이블의 레코드의 저장 방식이라고 볼 수 있다.
프라이머리 키가 없는 InnoDB 테이블이 클러스터링 테이블 구성하는 법
- 프라이머리 키가 있으면 기본적으로 프라이머리 키를 클러스터링 키로 선정
- NOT NULL 옵션의 유니크 인덱스 중에서 첫 번째 인덱스를 클러스터링 키로 선정
- 자동으로 유니크한 값을 가지도록 증가되는 칼럼을 내부적으로 추가한 후, 클러스터링 키로 선택
세컨더리 인덱스에 미치는 영향
세컨더리 인덱스가 실제 레코드 주소를 가지고 있을 시 클러스터링 키값이 변경될 때마다 데이터 레코드의 주소가 변경되고 그 때마다 해당 테이블의 모든 인덱스에 저장된 주솟값을 변경해야한다.
이런 오버헤드를 제거하기 위해 InnoDB 테이블의 모든 세컨더리 인덱스는 해당 레코드가 저장된 주소가 아니라 프라이머리 키 값을 저장하도록 구현되어 있다.
클러스터링 인덱스의 장점과 단점
장점
- 프라이머리 키로 검색할 때 처리 성능이 매우 빠름
- 테이블의 모든 세컨더리 인덱스가 프라이머리 키를 가지고 있기 때문에 인덱스만으로 처리될 수 있는 경우가 많음 (커버링 인덱스라고 한다.)
단점
- 세컨더리 인덱스에 클러스터링 키를 갖기 때문에 클러스터링 키 값의 크기가 클 경우 전체적으로 인덱스 크기 커짐
- 세컨더리 인덱스 검색 -> 프라이머리 키 검색 -> 처리 성능 느림
- INSERT 할 때 프라이머리 키에 의해 레코드의 저장 위치가 결정되기 때문에 처리 성능이 느림
- 프라이머리 키를 변경할 때 레코드를 DELETE 하고 INSERT하는 작업이 필요 성능이 느려짐
기본적으로 인덱스는 항상 쓰기 성능을 희생해서 읽기 성능을 늘린다는 사실을 인지하자. 기본적으로 웹 서비스 같은 온라인 트랜잭션 환경에서는 쓰기에 비해 읽기의 비율이 높기 때문에 빠른 읽기를 유지하는 것이 맞다.
클러스터링 테이블 사용시 주의사항
- 클러스터링 인덱스 키의 크기
- 프라이머리 키가 커지면 세컨 더리 인덱스도 자동으로 커짐
- 모든 세컨더리 인덱스가 프라이머리 키 값을 포함한다.
- 세컨더리 인덱스는 늘 클러스터링 인덱스 키를 가진다는 사실을 인지하자.
- 프라이머리 키는 AUTO-INCREMENET 보다는 업무적인 칼럼으로 생성
- 이 부분은 근데 좀 고려할 필요가 있을 듯하다. 물론 프라이머리 키로 자주 사용되는 칼럼을 사용하면 성능 상 이점을 얻을 수 있겠지만 정책적인 변경이 생겨서 칼럼이 더 이상 프라이머리 키로 사용될 수 없다면 PK를 재설정 하는 과정에서 더 많은 cost 가 소모될 수 있다.
- 프라이머리 키는 반드시 명시할 것
- PK가 없는 테이블을 만들어도 어짜피 내부적으로 PK는 생성된다.(위에서 설명) PK로 얻을 수 있는 이점이 굉장히 크기 때문에 무조건 PK를 만들도록 하자.
- 프라이머리 키가 길어져도 세컨더리 인덱스가 필요하지 않다면 그대로 사용해도 좋다. 하지만 이 PK 자체가 커질 때 B-Tree가 커지는 것 정도는 고려해볼 필요가 있을듯.
외래키
InnoDB 스토리지 엔진에서만 생성할 수 있다. 외래키 제약이 설정되면 자동으로 연관되는 테이블의 칼럼에 인덱스까지 생성된다. -> 실제로 외래키 제약 조건을 걸면 알아서 index가 생성 된다. 이 때문에 생각보다 우리가 인덱스를 직접 걸지 않아도 인덱스를 효율적으로 이용하고 있는 경우가 많다.
- 테이블의 변경이 발생하는 경우에만 잠금 경합이 발생
- 외래키와 연관되지 않은 칼럼의 변경은 최대한 잠금 경합을 발생하지 않음
자식 테이블의 변경이 대기 하는 경우
자식 테이블의 외래키 칼럼의 변경은 부모 테이블의 확인이 필요한데, 이 상태에서 부모의 테이블의 해당 레코드가 쓰기 잠금이 걸려 있으면 해당 쓰기 잠금이 해제될 때까지 기다리게 되는 것이다.
부모 테이블의 변경 작업이 대기하는 경우
자식 테이블이 생성될 때 정의된 외래키의 특성 대문에 부모레코드가 삭제되면 자식 레코드도 동시에 삭제되는 식으로 작동하기 때문이다.
데이터 베이스에서 외래 키를 물리적으로 생성하려면 이러한 현상으로 인한 잠금 경합까지 고려해 모델링을 진행하는 것이 좋다. 이처럼 물리적으로 외래키를 생성하면 자식 테이블에 레코드가 추가되는 경우 해당 참조키가 부모 테이블에 있는지 확인한 다는 것은 이미 다들 알고 있을 것이다. 하지만 물리적인 외래키의 고려 사항은 이러한 체크 작업이 아니라 이러한 체크를 위해 연간 테이블에 읽기 잠금을 걸어야 한다는 것이다. 또한 이렇게 잠금이 다른 테이블로 확장되면 그만큼 전체적으로 쿼리의 동시 처리에 영향을 미친다.
출처
Real My SQL(1)
