MYSQL B-tree Index(인덱스)

인덱스(index)란

대표적인 예시로 책의 맨 끝에 있는 “색인"정도로 설명할 수 있다.책의 색인에 표시 된 페이지수는 데이터 파일에 저장된 레코드 번호정도로 이해하면 된다.

인덱스는 기본적으로 칼럼의 값과 해당 레코드가 저장된 주소를 key-value 형식으로 인덱스를 만들어둔다. 인덱스는 SortedList 방식과 같은 형태로 저장되기 때문에 저장할 때 마다 정렬을 해줘야 하기 때문에 저장과정이 복잡하고 느리다.

인덱스를 사용하는건 데이터의 저장(Insert,Update,Delete) 성능을 어느정도 희생해서 데이터 읽기 속도를 올리는 기능이라고 보면 된다. 그렇다고 무작정 Where 절에 들어가는 칼럼을 모두 인덱스로 설정하게 되면 저장 성능이 현저히 떨어지고 인덱스 크기가 비대해져 역효과만 불러온다.

이제 인덱스의 가장 대표적인 알고리즘 B-Tree알고리즘을 한번 알아보자

B-Tree index

B-Tree index는 데이터베이스에서 가장 일반적으로 사용되고 있고, 가장 먼저 도입된 알고리즘이다. B-Tree 는 칼럼의 원래 값을 변형시키지 않고 인덱스 구조체 내에서 항상 정렬된 상태로 유지한다. 일반적으로 DBMS 에서 주로 B+-Tree 또는 B*-Tree가 사용된다. 다들 위 그림처럼 B-Tree 그림을 봐서 Binary 라고 생각 하는 분들도 계신데 B는 “Balanced”를 의미한다.

구조 및 특징

https://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/

B-Tree 는 트리 구조이며 최상위에 “root Node” 가 존재하고 그 하위에 자식 노드가 붙어 있는 형태이고 ,“branch Node” 라는 중간 노드와 “leaf Node” 라는 최하위 노드가 존재한다.

데이터베이스에서 인덱스와 실제 데이터는 따로 관리가 되는데 leaf Node는 실제 데이터의 주소를 가지고 있다. leaf Node 아래에 데이터파일이 존재하는데 데이터 파일은 따로 정렬이 되어있지 않다. 데이터 파일은 insert 순서대로 저장이 되긴하지만 무조건 보장이 되는 것은 아니다.

만약 데이터를 한번도 삭제,수정이 없었던 경우는 가능할지도 모르지만 insert 데이터는 들어올때 만약 기존 있던 데이터가 삭제된 공간이 있으면 그 공간을 재활용한다. 그래서 항상 insert 순서대로 입력되는건 아니다.

그리고 인덱스는 키 칼럼값만 가지고 있으므로 나머지 칼럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아와야한다. 그렇다면 만약 인덱스를 걸어둔 칼럼만 가지고 온다면 데이터 파일까지 갈 필요가 없지 않겠는가? 맞다

인덱스가 걸린 칼럼만 가져오거나 count를 한다면 굳이 실제 데이터 파일까지 들어가지 않아 성능이 올라간다.

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

> 인덱스 키 값 크기

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라고 부른다. 디스크에서 모든 읽기 및 쓰기 작업의 최소 작업 단위이다. 이 페이지 안에 인덱스 키 값이 들어가게 되는데 페이지 용량은 무한하지 않기 때문에 만약 키 값이 커지게 되면 디스크로 부터 읽어야 할 횟수가 늘어나게 되고 그만큼 느려지게 된다.

만약 페이지(16KB)안에 넣는다고 가정을 하면 키값이 12바이트라고 가정하면 약 585개의 키값 저장이 가능하다. 하지만 키 값이 32바이트일 경우에는 372개의 키값만 한 페이지에 저장이 가능하다. 만약 500개의 레코드를 스캔한다면 전자는 1번만 하면 되고 후자는 2개의 페이지를 디스크로 부터 읽어야 한다.

> 기수성(Cardinality)

모든 인덱스 값 가운데 유니크한 값의 수를 의미한다. 우선 결론부터 말하자면 기수성은 높을수록 좋다. 1000개의 인덱스 키값중 100개가 유일값이라면 기수성은 10이 된다. 왜 기수성이 높으면 좋은지 보자.

만약 1000개의 데이터에 10개의 유일한 키값을 가진 인덱스가 있다하면 특정 데이터를 조회시 1개의 값 조회를 위해 99개의 값을 더 읽어야한다.

만약 100개의 유일한 키 값을 가진 인덱스가 존재한다면 데이터를 읽을 때 9개만 더 읽게 된다.

이것만 봐도 확 느껴진다. 지금은 수가 그렇게 크지 않지만 데이터가 많아지게 되면 더더욱 신경을 써야하는 부분이다.

그리고 인덱스를 통해 읽는 데이터는 전체 레코드에 20%–25%를 넘어서면 테이블 데이터를 전체를 읽어서 필터링 해내는게 더 효율적이다.

인덱스 키 추가

새로운 키 값이 B-Tree 에 저장될 때 테이블의 스토리지 엔진에 따라 새로운 키 값이 저장될 수도 있고 아닐수도 있다. B-Tree에 저장될 때는 저장될 키값을 통해 적절한 위치를 찾아서 키값과 대상 레코드의 주소값을 leaf Node에 저장한다.

만약 leaf Node가 꽉 차서 넣을수 없다면 리프노드를 분리해서 저장을 해줘야한다. 이런 동작들 때문에 인덱스를 사용하면 입력 작업 성능이 떨어지게 된다.

인덱스 키 변경

인덱스의 키 값은 leaf Node를 결정하는 값이기도 해서 단순 변경은 불가능하다.만약 변경을 하려면 우선 키값을 삭제하고 새로운 키 값을 입력해주는 형태이다.

변경이라곤 하지만 실질적으로 삭제 후 새로 입력이다.

인덱스 키 삭제

B-Tree의 키 값이 삭제되는 경우는 해당 키 값이 저장된 B-Tree 의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료 된다. 이렇게 삭제 마킹이 된 인덱스 키 공간은 재활용이 가능하다.

위에서 말한것 처럼 입력된 순서대로 저장이 보장되지 않는 이유가 이런 재활용 때문이다.

인덱스 키 검색

우리가 인덱스를 사용하는 이유는 입력 동작은 조금 성능이 떨어지더라도 읽기 성능을 올리기 위해서이다.

B-Tree는 Root Node부터 시작해 Branch Node를 거쳐 leaf Node까지 이동하면서 비교작업을 수행하는데, 이 과정을 “트리 탐색"이라고 한다. 인덱스 검색은 부등호 (<,>)비교 조건에서도 인덱스를 활용할 수 있지만, 인덱스를 구성하는 키 값의 뒷부분만 검색하는 용도로는 인덱스를 사용할 수 없다.

또한 인덱스를 이용한 검색에서 키값이 변형이 가해진 경우에는 인덱스에 존재하는 값이 아니기 때문에 사용이 불가능하고 B-Tree의 장점을 활용할 수 없게 된다.

추가로 Inno DB 테이블에서 지원하는 Record Lock이나 Next Key Lock이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현되어 있기 때문에 수정이나 삭제 과정을 수행할 때 적절한 인덱스가 없으면 불필요하게 많은 데이터가 잠기게되고 최악의 상황은 전체 데이터를 잠글수도 있다는 것이다. Inno DB에서는 인덱스 설계가 매우 중요하다.

인덱스를 통한 데이터 읽기

index range scan

인덱스의 접근 방법 중 가장 대표적인 방법이고 index full scan, loose index scan 보다 빠른 방식이다. 인덱스 레인지 스캔은 검색해야 할 인덱스의 범위를 우선적으로 결정한 후 탐색을 한다.

루트 노드에서부터 비교를 시작해 브랜치 노드를 거쳐서 최종적으로 리프 노드까지 들어가야만 필요한 레코드의 시작 지점을 알 수 있다. 리프노드에서 시작점을 찾았다면 거기서부터 순차적으로 읽는다. 그리고 해당 리프노드에 데이터가 없다면 리프노드간 링크를 이용해 다음 리프노드로 넘어가서 다시 스캔한다.

그리고 범위가 끝났다면 조건에 맞는 레코드를 반환하고 쿼리가 마무리 된다. 여기서 필요한 레코드를 리턴하게 되면 인덱스 주소를 통해 랜덤I/O가 데이터 갯수 만큼 발생한다.

index full scan

이름 그대로 인덱스를 전체 스캔하는 방식이다. 이 경우는 쿼리에 조건절이 사용된 칼럼이 첫번째 칼럼이 아닌 경우 인덱스 풀 스캔으로 동작한다. 인덱스 풀 스캔은 레코드를 가져오는 경우에는 절대로 사용하지 않고 인덱스에 포함된 칼럼만 가지고 올 경우에만 사용된다.

loose index scan

MYSQL 8.0 버전부터 최적화 된 버전으로 나온 스캔이다. 루스 인덱스 스캔은 인덱스 레인지 스캔과 비슷하지만 중간에 필요하지 않은 데이터는 스킵하고 다음으로 넘어간다. 일반적으로 Groupby나 MAX(),MIN()함수에 대해 최적화 시 사용한다.

index skip scan

Real Mysql 8.0 -238p

이것도 MYSQL 8.0 버전부터 나온 스캔이다. 기존에는 인덱스의 첫번째 칼럼이 없으면 새로 만들거나 했어야 했다. 하지만 인덱스 스킵 스캔은 첫번째 칼럼이 아닌 두번째 칼럼으로도 인덱스 스캔이 가능하도록 해준다.

인덱스 스킵 스캔은 만약 두번째 칼럼으로 조회하게 된다면 첫번째 칼럼의 유니크한 값을 모두 조회해서 첫번째 칼럼에 조건을 추가해서 쿼리를 다시 실행하는 형태로 처리한다.

 

마치며

인덱스는 진짜 양날의 검이다. 사용을 잘못하면 오히려 가만히 두는거보다 더 안좋은 성능을 낼수도 있다. DBA가 따로 없는 경우에는 백엔드가 그냥 크게 고민 안해보고 구성하는 경우가 더러있다. 하지만 이왕이면 잠깐만 고민하고 공부해도 효율적으로 사용 할 수 있는데 안할 이유는 없는것 같다.

참고

Real Mysql 8.0 (꼭 사세요. 진짜 내용 좋음) — https://product.kyobobook.co.kr/detail/S000001766482