Real MySQL 8.0을 보고 정리하는 내용입니다.

인덱스란?

• DBMS에서 인덱스는 데이터의 저장(INSERT, UPDATE, DELETE) 성능을 희생하고 그 대신 데이터의 읽기 속도를 높이는 기능
• SELECT 쿼리 문장의 WHERE 조건절에 사용되는 컬럼이라고 전부 인덱스로 생성하면 데이터 저장 성능이 떨어지고 인덱스의 크기가 비대해져 오히려 역효과만 불러올 수 있음
• 대표적으로 B-Tree 인덱스와 Hash 인덱스로 분류를 나눌 수 있음. 최근에는 Fractal-Tree 인덱스나 로그 기반의 Merge-Tree 인덱스와 같은 것들도 사용됨

B-Tree 알고리즘 기반
column의 값을 변형하지 않고 인덱싱하는 알고리즘.

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

B-Tree 인덱스

• 가장 일반적으로 사용되는 알고리즘
• B+ Tree 또는 B* Tree가 일반적으로 사용됨
• 전문 검색과 같은 특수한 요건이 아닌 경우 대부분 B-Tree를 사용함

B-Tree 구조 및 특성

• 최상위에 하나의 '루트 노드', 최하위에 '리프 노드', 그 외의 '브랜치 노드'로 이루어짐
• 최하위의 '리프 노드'는 항상 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있음

[Real MySQL 8.0 1권 그림 8.4]

• 인덱스 키 값은 정렬되어 있음. 하지만 데이터 파일의 레코드는 INSERT된 순서대로 저장되는 것이 아님.
• 인덱스는 테이블의 키 column만 가지고 있으므로 나머지 column을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 함. 이를 위해 리프 노드는 데이터 파일에 저장된 레코드의 주소를 가짐.

[Real MySQL 8.0 그림 8.6]

• InnoDB 테이블에서 인덱스를 통해 레코드를 읽을 때는 인덱스에 저장돼 있는 프라이머리 키 값을 이용해 프라이머리 키 인덱스를 한 번 더 검색한 후, 프라이머리 키 인덱스의 리프 페이지에 저장돼 있는 레코드를 읽음.(위 그림 참고)

B-Tree 인덱스 키 추가

• 새로운 키 값이 B-Tree에 저장될 때 테이블의 스토리지 엔진에 따라 새로운 키 값이 즉시 인덱스에 저장될 수도 있고 그렇지 않을 수도 있음.
• B-Tree에 저장될 키 값을 이용해 적절한 위치를 검색하고, 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree 리프 노드에 저장함.
• 리프 노드가 꽉 차서 더 저장할 수 없을 땐 리프 노드가 분리돼야 하는데, 이는 상위 브랜치 노드까지 처리 범위가 넓어짐.
• InnoDB 스토리지 엔진은 필요하다면 키 추가 작업을 지연시켜 나중에 처리함. 하지만 Primary key나 Unique index의 경우 중복 체크가 필요해 즉시 B-Tree에 추가하거나 삭제함.

B-Tree 인덱스 키 삭제

• 해당 키 값이 저장된 B-Tree 리프 노드를 찾아 삭제 마크를 함
• 삭제된 공간은 방치되거나 재활용됨
• MySQL 5.5 이상 버전의 InnoDB 스토리지 엔진에선 삭제 역시 지연처리될 수 있음

B-Tree 인덱스 키 변경

• 키 값 삭제 후 새로운 키 값을 추가하는 형태로 처리됨

B-Tree 인덱스 키 검색

• B-Tree의 루트 노드로부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행('트리 탐색'이라 함)
• SELECT 뿐만 아니라 UPDATE나 DELETE 쿼리를 처리하기 위해 항상 해당 레코드를 먼저 검색해야 할 경우에도 사용됨
• 키 값 전부 혹은 키 값의 앞부분이 일치하는 경우 B-Tree 인덱스를 이용한 검색을 할 수 있음. 키 값의 뒷부분만 검색하는 용도로는 인덱스를 사용할 수 없음.
• InnoDB 테이블에서 지원하는 레코드 잠금이나 넥스트 키락(갭락)이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현되어 있음. 따라서 UPDATE나 DELETE 쿼리 시 적절히 사용할 수 없는 인덱스가 없으면 불필요하게 많은 레코드를 잠구게 됨.

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

B-Tree 인덱스는 인덱스를 구성하는 column의 크기와 레코드 건수, 그리고 유니크한 인덱스 키 값의 개수 등에 의해 검색이나 변경 작업의 성능이 영향을 받음

인덱스 키 값의 크기

• InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 Page또는 Block이라고 함. 이는 디스크의 읽기 및 쓰기 작업의 최소 단위가 됨.
• 인덱스 키 값의 크기가 커지면 하나의 페이지에 저장할 수 있는 키의 개수가 적어짐. 키 값이 커지면 Page를 여러 번 읽을 수 있고, 그만큼 느려진다는 것을 의미함
• 인덱스 키 값의 길이가 커진다는 것은 전체 인덱스의 크기가 커진다는 것을 의미. 인덱스를 캐시해두는 InnoDB의 버퍼 풀은 크기가 제한적. 따라서 인덱스 크기가 커지면 메모리에 캐시할 수 있는 레코드 수는 줄어들어 메모리 효율이 떨어지는 결과를 야기함.

B-Tree 깊이

• 인덱스 키 값의 크기가 커지면 Page가 많아지고, 이는 B-Tree의 깊이가 깊어진다는 것을 의미함. B-Tree의 깊이는 조회에서 디스크를 몇 번 읽어야 하는지와 직결된 문제임. 이는 결국 성능 저하와 관련이 있음
• 하지만 아무리 대용량의 데이터베이스라도 B-Tree의 깊이는 5depth 이상 깊어지긴 쉽지 않음

Cardinality(Selectivity)

• 인덱스 키 값 중 중복된 값이 많으면 Cardinality(기수성)은 낮아짐. 1건의 요구조건에 만족하는 데이터를 찾아야 하는데 기수성이 낮은 인덱스를 사용할 경우 많은 필요없는 데이터가 함께 조회됨. 따라서 기수성이 높은 column을 인덱스 키 값으로 정하는게 중요함.

SELECT * FROM tb_test
WHERE country = 'KOREA' AND city = 'SEOUL';

1. country의 중복값이 10개인 경우
   country = 'KOREA'로 검색한 10개의 데이터 중 9개는 필요없는 데이터
2. country의 중복값이 1000개인 경우
   country = 'KOREA'로 검색한 1000개의 데이터 중 999개는 필요없는 데이터

즉 country = 'KOREA' && city = 'SEOUL'를 만족하는 데이터가 단 하나라면 1번의 경우가 10개만 확인하면 원하는 데이터를 얻을 수 있기 때문에 더 효율적이다.

• Cardinality가 좋지 않더라도 정렬이자 Grouping을 위해 인덱스를 만드는 것이 훨씬 나은 경우도 있음. 인덱스는 검색에만 사용되는 것이 아니므로 여러 가지 용도를 고려해 적절히 인덱스를 설계할 필요가 있음

읽어야 하는 레코드의 건수

테이블에 레코드가 100만 건 저장돼 있는데 그 중 50만 건을 읽어야 한다면?
전체 테이블을 읽어 50만 건을 버리는 것이 효율적인지, 인덱스를 통해 필요한 50만 건만 읽어 오는 것이 효율적인지 판단해야 함.
보통 전체 테이블 레코드의 20~25%를 넘어가면 전체 테이블을 읽어 필요한 레코드를 가려내는 방식이 효율적이라고 함.
MySQL의 옵티마이저가 최적의 방법을 선택하겠지만, 알아두는게 좋음