[MySQL] DB Index A to Z, 인덱스의 모든 것.
모-하🤎
안녕하세요. 모던 애자일 대표 겸 1기 회장 겸 백엔드 팀장 우리밋입니다.
이번엔 모던 애자일의 팀원으로서 첫 글을 포스팅해보려 합니다 😁
서론
1기 팀 내에서 운영 중인 서비스를 성능면에서 최적화를 시켜보고자 인덱스를 도입하였는데요.
기존에도 인덱스는 잘 적용이 되고 있었지만, “~~카더라” 라는 개념으로 적용을 했던 것이어서 기술적으로 더 Deep하고 프로젝트 환경에 맞게 최적화를 시켜보고자 인덱스를 처음부터 다시 공부를 해보았습니다.
여러분들도 잘 아시다시피, DB의 최적화를 위해 가장 일반적으로 검토하는 부분이 Index인데요.
Index만 프로젝트 환경에 맞춰 잘 도입한다면, 서비스의 성능이 수십배 아니 수백배 까지 향상될 수 있습니다.
음.. 모든 속도가 수백배로 향상되는 것은 아니고, Index가 도입된 Query문이 실행됐을 때의 이야기입니다.
아무튼, DB 최적화의 일등 공신 Index를 알아보도록 합시다.
INDEX란
INDEX는 책의 목차/색인 이라고 생각하면 쉽다.
아래는 인덱스를 1도 모르는 “무”의 경지에서 “아는 척”의 경지로 만들어주는 유익한 영상이다.
꼭 시청 후 아래 포스팅을 이어서 보도록 하자.
INDEX 장단점
장점
(1) 검색(Select) 속도가 빨라진다. (항상 그런 것은 아니다.)
(2) 인덱스가 포한된 Query 문 실행 시 속도가 대폭 향상되는데, 이는 곧 전체 서비스 성능 향상으로 이어진다.
DB에서 데이터 조회를 빨리 할 수 있다는 것은 Client에게 빠르게 데이터를 보내줄 수 있다는 것이고, 이것은 Client가 사용자에게 더 빠르게 데이터를 제공해줄 수 있다는 말이 된다.
단점
(1) CRUD의 R(read)만 성능 개선이 이루어지고, C(create), U(update), D(delete)는 성능이 약간 저하된다.
(2) 따라서, 데이터의 변경 작업이 자주 일어날 경우 오히려 성능이 나빠질 수도 있다.
(3) 인덱스가 생성될 때 DB의 공간을 차지하기 때문에 10% 정도의 여유 공간이 필요하다.
(4) 마찬가지로, 인덱스가 생성되는 시간이 많이 소요될 수 있다.
R만 성능 개선이 이뤄지고, CUD는 저하된다는 개념의 원리 이해는 기술적으로 더 Deep하게 이해하게 되면 자연스럽게 깨달을 수 있다. 또한, 장단점 모두는 인덱스의 원리를 이해하면, 모두 알 수 있는 것들이다. 고로, 끝까지 읽길 바란다.
INDEX의 종류
INDEX를 공부하기 앞서 기존의 알고있는 개념과 연결지어 생각해본다면, 이후에 좀 더 이해하기 수월할 것이다.
사실은, 우린 이미 INDEX를 사용하고 있었다.
바로 PK와 FK인데, 이 둘은 서로 다른 종류의 INDEX가 부여되어 있다.
PK는 Clustered Index이며, FK는 Non-Clustered Index이다.
깊게 들어가면 PK가 꼭 Clustered Index가 아닐 수도 있지만, 아무런 설정을 하지 않았을 때는 자동으로 PK에 Clustered Index가 부여된다는 것을 기억하고 이어서 보도록 하자.
이쯤에서 Clustered Index와 Non-Clustered Index를 구분지어 설명하고자 했으나, 온전히 이해하기 위해서는 Index 생성에 사용되는 자료구조를 먼저 살펴보는 것이 우선이라 생각된다.
따라서, Index에 사용되는 자료구조인 B+tree를 먼저 살펴보겠다.
INDEX 자료구조 B+tree
MySQL의 DB Engine인 InnoDB는 B+tree로 이뤄져있는데, 이는 B-tree의 확장된 개념이다.
따라서, B-tree부터 살펴보자.
B-tree
B-tree 자료구조는 기본적으로 트리 구조로 되어있다.
위의 사진이 트리 자료구조의 일반적인 모습이다.
[그림 1]에 표시된 사각형은 각각 노드(Node)라고 한다.
가장 상단의 노드를 루트 노드(Root Node), 중간 노드들을 브랜치 노드(Branch Node), 가장 하단 노드들을 리프 노드(Leaf Node)라고 한다.
이진 트리(binary-tree) 자료구조를 이해하고 있다면 훨씬 이해하기 수월할 것이다.
B-tree와 이진 트리와의 차이점을 얘기하자면, 위의 사진 처럼 자식 노드가 2개가 아닐 수 있다는 것이다.
트리 구조는 검색에 필요한 I/O 동작 회수를 줄일 수 있다는 장점이 있어서 검색이 빈번히 일어나는 프로그램을 구현할 때 효과가 좋다. 일단은 “아, 그렇구나” 하고 넘어가자.
B-tree는 Binary-tree와 유사하지만, 한 노드당 자식 노드가 2개 이상이어야만 한다.
B-tree는 빠르다.
B-tree는 어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있다.
[그림 2]의 B-tree에서 ‘1’과 ‘10’을 찾는 시간은 동일하다. 다만, Tree 높이가 다른 경우에는 약간의 차이가 발생한다. 기본적으로 O(logN) 시간 복잡도를 갖는다.
선형 탐색과 비교해보자.
[1, 2, 3, 4 … 10, 11 … 99, 100]
이라는 배열에서 ‘1’과 ‘10’을 찾기 위해서는 배열을 순회하며 하나씩 값을 확인해주어야 한다.
선형 탐색은 기본적으로 O(n)의 시간 복잡도를 갖게 된다.
이는 데이터가 100만개가 있을 때 100만 번째 데이터를 찾으려면 100만개의 데이터를 모두 순회해야한다는 것이다.
풀 스캔이 선형 탐색, 인덱스 스캔이 B-tree 탐색 이라고 보면 된다.
인덱스 스캔은 레인지(Range) 스캔이라는 말로 더 많이 불리고 있다.
데이터의 양이 증가할 수록 검색에서의 장점은 부각된다.
B+tree
B+tree 자료구조는 B-tree의 확장된 개념이다.
B-tree와의 가장 큰 차이점은 데이터가 저장되는 위치다.
B-tree는 데이터가 branch 노드와 leaf 노드 어디든 담길 수 있지만, B+tree는 leaf 노드에만 데이터가 저장된다.
[그림 4]에서 ‘d’는 데이터를 의미하며, 숫자는 노드를 의미한다.
숫자를 감싸고 있는 컨테이너는 페이지라고 부른다.
즉, 페이지별로 여러 노드가 생성되며, 각 노드는 key와 value의 형태를 유지한다.
여기서는 회색박스가 key고 흰 박스가 value이다. (회색과 흰색의 개수가 일치하지 않는 것은 단순히 이해를 돕기위한 그림이라 그렇다)
보다시피 리프 페이지들 끼리는 Linked List로 연결되어 있다.
따라서, Linked List를 통해 리프 노드들끼리의 선형 탐색으로 데이터를 찾을 수도 있다.
InnoDB에서 사용되는 B+tree의 구조는 이보다 복잡한 구조로 되어있다.
Double Linked List와 Single Linked List의 조합으로 이루어져 있는데, 이는 개인적으로 찾아보길 권한다.
# 보충
트리 구조는 기본적으로 key 와 value로 구성되어 있다.
이는 인덱스에 사용되는 자료구조가 Key와 Value로 구성 되어있다는 말을 의미한다.
B+tree에서의 key와 value에 대해 간략하게 알려주자면, (여기서 페이지는 노드들을 담고있는 컨테이너로 이해하면 된다) 루트 노드의 key는 Clustered Index로 설정된 컬럼명이고, value는 다음 페이지 번호이다. 브랜치 노드의 key는 자신 노드의 컬럼명이고, value는 다음 페이지 번호이다. 리프 노드의 key는 자신 노드의 컬럼명이고, value는 실제 데이터 값이다. 다만, 이는 Clustered Index에서의 key:value 이다.
Non-Clustered Index에서는 리프 노드의 value가 실제 데이터 값이 아닌 Clustered Index의 컬럼명으로 되어있다. (이해가 안될 수 있다. 보다보면 좀 더 자세한 설명이 나올 것이다.)
B+tree의 장점
1. 리프 노드를 제외하고 데이터를 담아두지 않으므로 메모리 확보에 유리하고, 더 많은 key들을 수용할 수 있다.
-> 즉, 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다.
-> 트리의 높이가 낮다면, 데이터가 방대해지더라도 B-tree에 비해 검색 속도를 더 빠르게 유지할 수 있다.
-> 기본적으로 B+tree의 높이는 3을 유지한다고 한다.
2. 데이터 검색 시 B-tree는 모든 노드를 뒤지며 데이터를 확인해봐야되는 반면에, B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 탐색으로 데이터를 찾을 수 있다.
-> 즉, B-tree보다 빠르다.
INDEX의 종류
인덱스 자료구조인 B+tree에 대해 이해했다면, Clustered Index와 Non-Clustered Index를 이해하는데는 크게 어려움이 없을 것이다. 아래에서 설명되는 Clustered 와 Non-Clustered는 B+tree 자료구조에 기반하여 설명되며, 트리 구조는 key:value 형태로 이루어져있다는 것을 기억한 채로 보길 바란다.
Clustered INDEX
(1) 한 테이블 당 하나의 Clustered Index만 생성이 가능하다.
(2) Clustered Index를 임의로 지정하지 않는다면, PK가 Clustered Index로 설정된다.
(3) 행(row) 데이터는 Clustered Index로 지정한 열(culumn)에 맞춰 자동 정렬된다.
-> 데이터 삽입 시 정렬된 위치에 맞춰 삽입되어야 하므로 단순 삽입보다 시간이 더 소요된다.
[그림 5] 처럼 리프 페이지 각 노드의 value에만 실제 데이터가 저장되며, 그 외 노드(페이지)의 value에는 페이지 번호(RID)가 저장된다. 또한, 데이터가 Clustered Index 순서에 맞춰 정렬이 되어있기 때문에 검색 시 굉장히 빠르게 값을 읽어올 수 있다.
여기서 기억해야 할 것은, 데이터가 정렬되어있는 기준이 Clustered Index라는 것이다.
다시 말해, Non-Clustered Index를 기준으로 정렬되는 것이 아니라는 것을 알아야 한다.
따라서, Clustered Index로 검색할 때 Non-Clustered Index 보다 더 빨리 데이터를 읽어올 수 있게 된다.
다만, 장점이 있으면 단점도 있듯이 R(read)는 빠르지만 C(create), U(update), D(delete)는 Non-Clustered Index보다 비교적 느리게 동작한다.
Non-Clustered INDEX (=Secondary Index)
(1) 한 테이블에 여러 Non-Clustered Index를 생성할 수 있다.
(2) 여러 속성(Attribute)를 묶어서 복합 인덱스를 만들 수도 있다.
(3) FK는 Non-Clustered Index이다. (Clustered Index를 제외한 모든 인덱스는 Non-Clustered Index이다)
(4) 리프 노드의 value에는 실제 데이터 값이 저장되는 것이 아니라, Clustered Index의 컬럼명이 저장되어있다.
-> 즉, Non-Clustered Index로 리프 노드까지 탐색을 마치면 Clustered Index의 컬럼명을 알 수 있는 것이고, 이를 통해 Clustered Index를 한 번 더 탐색하게 된다.
-> 따라서, Clustered Index보다 탐색 속도가 느릴 수 밖에 없다. 데이터의 입력/수정/삭제는 더 빠르다.
[그림 6]을 보면 리프 페이지의 value에 실제 데이터가 아닌 페이지 번호(RID)가 저장되어 있는 것을 알 수 있다.
이처럼, Non-Clustered Index에는 실제 데이터가 저장되지 않는다.
여기서 조심해야할 것은, 위 사진에서 리프 노드의 value로 페이지 번호(RID)가 저장되어 있지만, 실제로는 Clustered Index의 컬럼명이 저장된다. (혹시나 아니라면 댓글로 부탁드립니다)
따라서, [그림 6] 사진은 단순히 “Non-Clustered Index에는 데이터가 저장이 되지 않는구나”를 이해하는 용도로만 보길 바란다.
아래 사진을 보면 인덱스의 전반적인 구성을 이해할 수 있을 것이다.
위 사진을 보면, 결국에 Non-Clustered Index에서 데이터를 찾을 때도 Clustered Index를 탐색한 뒤에 최종 데이터에 접근할 수 있는 것을 알 수 있다.
INDEX의 삽입, 삭제, 수정
인덱스를 사용하는 이유는 검색(조회)의 성능을 대폭 향상시키기 위함이다.
DB의 데이터가 많을 수록 효과는 좋아진다.
그렇다면, “모든 Attribute(속성)에 INDEX를 부여하면 좋지 않겠는가?” 라고 생각하진 않았겠지만, 역시나 좋지 않다.
인덱스로 설정된 Attribute(속성)은 검색 시에는 굉장히 빠르지만, 삽입, 삭제, 수정 시에는 비교적 속도가 느려진다. 이유를 알아보자.
INDEX의 삽입, INSERT
지금까지의 내용들이 이해됐다면, 실제 데이터는 Clustered Index에만 저장된다는 것을 알았을 것이다.
따라서, 데이터의 삽입을 설명하기 위해 Clustered Index의 관점에서 얘기하겠다.
이해하기 쉽도록 정렬된 배열을 예로 들어보겠다.
[1, 3, 5, 6, 8, 9, 13, Null]
과 같은 배열이 있을 때 “7을 추가하기 위해서는 어떤 작업을 거쳐야 할까”를 고민해보자.
당연히, 6과 8 사이에 ‘7’이 삽입되어야 하므로 8, 9, 13 은 뒤로 밀고 8번이 있던 원래 위치에 7을 넣어주어야 할 것이다.
그럼 아래와 같이 될 것이다.
[1, 3, 5, 6, 7, 8, 9, 13]
생각해보면 8, 9, 13을 하나씩 뒤로 밀면서 불필요한 시간이 소요됐다.
이번에는 2를 추가해보자.
추가하려고보니 배열의 빈 공간이 없다.
어떻게 할까 고민을 해보니, 13을 새로운 배열에 넣어주고 3~9까지 한 칸씩 뒤로 밀어주면 될 것 같다.
[1, 2, 3, 5, 6, 7, 8, 9] -> [13]
이처럼 말이다.
여기서 문제는, 배열이 하나가 더 생겨났을 뿐더러 13을 새로운 배열로 옮기는 작업까지 필요했다. 3~9의 숫자를 한 칸씩 밀어준 시간도 필요했다.
Index의 삽인은 이러한 개념과 같다.
DB의 관점에서 숫자는 각 데이터인 행(Row)를 의미하고, 배열은 데이터를 담고있는 페이지라고 생각하면 된다.
페이지 별로 InnoDB에서는 각 16KB를 저장할 수 있다.
16KB가 넘어가면 새로운 페이지에 데이터를 저장해주게 되는 것이다.
INDEX의 삭제, DELETE
인덱스의 경우 데이터가 지워지지 않고 “사용되지 않음” 표시만 해준다고 한다.
메모리 공간의 낭비를 초래한다.
INDEX의 수정, UPDATE
인덱스에는 수정(update)라는 개념이 없다.
삭제 -> 삽입의 과정으로 수정을 대신한다.
즉, 수정되어야할 데이터는 “사용되지 않음” 표시를 하고 (메모리 공간 낭비)
새로 변경된 데이터는 삽입된다. (시간 낭비)
INDEX 도입
Index는 검색이 굉장히 많이 일어나고 그에 비해 삽입, 수정, 삭제가 적게 발생하는 Attribute에 설정해주는 것이 좋다.
기본적으로는 카디널리티(cardinality)가 높은 Attribute에 설정해준다.
카디널리티(cardinality)
카디널리티가 높은 것 : 주민등록번호, 학번
카디널리티가 낮은 것 : 이름, 성별
즉, 중복의 정도를 생각하면 된다.
중복되는 데이터가 없을 수록 카디널리티는 높은 것이며, INDEX로 설정하기 좋은 Attribute이다.
카디널리티는 상대적인 개념이다.
성별보다는 이름이 카디널리티가 높기 때문에 성별에 비해 INDEX로 설정하기 좋다고 할 수 있다.
적용
PK는 Clustered Index, FK는 Non-Clustered Index 가 기본적으로 설정된다.
유일키(Unique Key)도 Non-Clustered Index이기 때문에 한 테이블당 여러 개를 생성할 수 있다.
유일키(Unique Key) 적용
CREATE UNIQUE INDEX 인덱스명
ON 테이블명 (속성명)유일 복합키(Unique Composite Key) 적용
CREATE UNIQUE INDEX 인덱스명
ON 테이블명 (속성명, 속성명)일반적인 인덱스(Index) 적용
CREATE INDEX 인덱스명
ON 테이블명 (속성명)복합 인덱스(Composite Index) 적용
CREATE INDEX 인덱스명
ON 테이블명 (속성명, 속성명, 속성명)지금까지 INDEX에 대한 개념을 다뤄보았습니다.
INDEX에서 알아야 할 이론의 거의 모든 것을 다뤘다고 생각하지만, 더 필요한 내용이 있다면 댓글로 말씀해주세요.
모던 애자일 1기 우리밋이었습니다.
모-바🤎
