[3주차] 속도를 지배하는 DB 인덱스
03. 인덱스란?
책갈피를 끼워두고 필요할 때 바로 해당 페이지를 펼 수 있게 하는 것과 같다. 즉, DB에서 자주 사용하는 필드 값의 위치를 저장해놓음으로써, 데이터를 빠르게 탐색할 수 있다. 탐색을 빠르게 할 수 있는 반면, 데이터가 추가될 때마다 책갈피를 꽂아 넣어야해서(인덱스 생성), 데이터의 탐색 속도는 빠르지만 데이터를 추가하는 속도는 느려질 수 있다.
인덱스의 적용 원리
서점에서는 어떤 기준으로 사람들이 책을 많이 찾나요? 바로 “카테고리” 이다. IT, 교육, 참고서, 요리 등등… 카테고리를 기준으로 책을 검색하고 싶어한다. 그래서 모든 책들을 책이라는 테이블에 등록할때, 인덱스에다가 많이 찾을 것 같은 속성들에 대해서 따로 다시 저장해둔다. 내가 관심 있어 하는 카테고리에 대해서만 저장해두면, 책들을 보면서 각 책들이 내가 원하는 카테고리인지 찾을 필요가 없다. 찾아야 하는 범위를 쉽게 알 수 있다.
book이라는 테이블에 id, name, category, price, is_adult, published_at 컬럼이 있는 경우를 가정해보자.
| id | name | category | price | is_adult | published_at |
|---|---|---|---|---|---|
| 1 | The Art of Computer | Technology | 35000 | false | 2015-03-10 00:00:00 |
| 2 | Midnight Secrets | Romance | 12000 | true | 2022-11-01 00:00:00 |
| 3 | Data Structures in Depth | Education | 28000 | false | 2018-07-22 00:00:00 |
| 4 | Blood and Betrayal | Thriller | 15000 | true | 2021-05-15 00:00:00 |
| 5 | Introduction to AI | Technology | 40000 | false | 2020-10-01 00:00:00 |
| 6 | Love in the Time of Code | Romance | 18000 | false | 2023-02-14 00:00:00 |
| 7 | Advanced Quantum Physics | Science | 50000 | false | 2019-01-30 00:00:00 |
| 8 | Forbidden Desires | Romance | 13000 | true | 2023-06-01 00:00:00 |
| 9 | The Algorithm Bible | Technology | 45000 | false | 2024-01-01 00:00:00 |
| 10 | Cursed Kingdoms | Fantasy | 22000 | true | 2022-09-10 00:00:00 |
그런데 요즘 들어서 유저들이 “카테고리” 와 “성인용” 두가지 칼럼을 기준으로 검색하는 경우가 늘어났다고 한다. 이런 경우에는, 두가지 칼럼을 대상으로 인덱스를 걸면 된다. 이를 복합 인덱스라고 한다. “성인용” 칼럼과 “카테고리” 칼럼 순서로 인덱스를 걸어보면 다음과 같다.
| is_adult | category |
|---|---|
| false | Education |
| false | Science |
| false | Technology |
| false | Technology |
| false | Technology |
| false | Romance |
| true | Fantasy |
| true | Romance |
| true | Romance |
| true | Thriller |
제가 만약 “Romance” 카테고리에 “성인용” 인 책을 찾아달라고 한다면 다음과 같은 과정이 이루어진다. 우선 is_adult 를 보니 성인용이니 카테고리를 확인하고 -> is_adult 를 보니 성인용이니 카테고리를 확인하고 -> is_adult 를 보니 성인용이니 카테고리를 확인하고, …. 너무 많은 검사를 하게된다.
이 문제의 원인은 is_adult 의 특별한 값의 종류가 너무 적기 때문이다. is_adult = true인 레코드가 너무 많아서 인덱스가 의미가 없어졌다. 오히려 특별한(unique) 값의 종류가 많은 것은 category이다.
Q. boolean 컬럼에 인덱스를 설정하면 성능에 유리할까요?
A. boolean 타입 필드에 인덱스를 설정하는 것이 성능상 유리할지는 데이터 분포와 쿼리 사용 패턴에 따라 다릅니다. 일반적으로 boolean 필드는 선택성이 낮아 인덱스를 설정하는 것이 성능 개선에 크게 도움이 되지 않을 수 있습니다. 하지만, 특정 쿼리에서 해당 필드를 자주 필터링하거나 균등한 데이터 분포가 있다면 인덱스를 설정하는 것이 성능에 도움이 될 수 있습니다.
만약 성능을 측정하고 최적화하는 과정에서 실제로 인덱스를 생성하는 것이 효과적이다는 결과가 나왔다면, 인덱스를 사용하는 것이 좋습니다. 그렇지 않다면, 불필요한 인덱스는 피하는 것이 좋습니다.
| category | is_adult |
|---|---|
| Education | false |
| Fantasy | true |
| Romance | false |
| Romance | true |
| Romance | true |
| Science | false |
| Technology | false |
| Technology | false |
| Technology | false |
| Thriller | true |
따라서 이번에는 “성인용” 칼럼과 “카테고리” 칼럼 순서가 아닌, “카테고리” 칼럼과 “성인용” 칼럼 순서로 복합 인덱스를 만들어보자. 만약 “만화” 카테고리에 “성인용” 인 책을 찾아달라고 한다면 아래 테이블에서 어떻게 찾게 될까? 우선 category 가 “Romance” 인 책들을 찾는다. -> 이때 다른 카테고리인 책들은 빠르게 걸러진다. -> 그리고 그 중에서 is_adult 인 책을 고르기만 하면 된다. 이처럼, 특별한 값의 종류가 많은 칼럼을 우선으로 복합 인덱스를 세워야 빠른 데이터 탐색이 가능하다.
05. 인덱스의 심화 이론
B-Tree
완전 이진 트리의 높이가 최대 O(log(N))임을 확인했습니다. 즉 ,탐색을 안정적으로 할 수 있는 장점이 있는 자료구조입니다. 그런데 이것보다 DB 에서 사용하기에 더 좋은 자료구조가 있습니다.
바로 Balance Tree(B-Tree) 라는 자료구조입니다. 관계형 DB 에서 자주 사용되는 구조이고, 면접 질문으로 정말 많이 듣는 형태이기 때문에 우리는 이에 대해서 이해하는 것이 좋습니다.
B-Tree는 이진 탐색 트리를 확장한 형태로, 하나의 노드가 여러 개의 키를 가질 수 있는 균형 트리이다. 모든 리프 노드가 동일한 레벨에 존재하며, 각 노드는 자식 노드에 대한 포인터를 포함한다. 이러한 구조는 RDBMS에서 가장 일반적으로 사용되는 기본 인덱스 구조이다.
B-Tree 는 다음과 같은 특징이 있다.
- 다중 키 저장: 각 노드는 여러 개의 키를 포함하며, 키들은 오름차순으로 정렬되어 있다.
- 자식 노드 분할: 노드의 키 개수가 N개라면, 해당 노드는 최대 N+1개의 자식 노드를 가질 수 있다.
- 균형 유지: 모든 리프 노드는 동일한 레벨에 위치하여 트리의 균형을 유지한다.