[DB] 쿼리 튜닝은 무엇인가 (2) - 인덱스 (B-tree와 B+tree)

지난 게시글에서는 쿼리 튜닝이 무엇인지에 대해 다루었고, 이번 게시글에서는 인덱스에 대해 이어서 정리하려고 한다. 지난 게시글은 아래 링크를 참고하면 된다.

https://wanna-developer02.tistory.com/218

[DB] 쿼리 튜닝은 무엇인가 (1) - 랜덤 I/O와 쿼리 튜닝

 

인덱스는 점프를 통해 데이터의 위치를 찾아내는데 그 원리는 무엇인지에 대해 정리해볼 예정이다. 목차는 다음과 같다.

• 정렬배열과 이진 탐색의 한계
• B-tree 와 B+tree 
• 클러스터드 인덱스와 세컨더리 인덱스

 

---

1. 정렬배열과 이진 탐색의 한계

어떤 데이터를 찾는다고 생각해보자. 아마 정렬된 배열에 값을 넣고 이진탐색을 하면 될것이다. 그럼 이론상 O(logn) 이기 때문에 나쁘지 않다. 하지만 디스크에는 두가지 문제가 있다.

 

1. 이진탐색은 비교할 때마다 배열의 멀리 떨어진 위치로 건너뛴다

100만건의 데이터에서 이진탐색을 하면 대략 20번의 비교가 이루어지는데, 곧 20번의 랜덤 점프가 이루어지는 셈이다. 계속 가운데 값으로 뛰다보니, 멀리 떨어진 위치로 뛰는게 된다.

 

2. 정렬 배열은 중간에 값을 하나 끼우려면 뒤를 전부 밀어야한다

즉, 삽입이 O(n) 이 된다. 게시글로 예시를 들었으니, 게시글이 생길 때마다 밀어야해서 사실상 사용할 수 없다.

 

 

보통 데이터의 삽입과 수정이 이루어지기 때문에 이진탐색은 힘들것이다. 그럼 다른 자료구조는 어떨까? 

• 해시인덱스
  • 검색이 O(1) 로 매우 빠르다. 하지만 해시는 순서가 사라지기 때문에 order by 정렬이 불가능하다.

• 일반 이진트리 / AVL 트리
  • 정렬이 가능하지만, 노드 하나에 키가 1개뿐이라 100만건의 데이터를 기준으로는 트리의 높이가 20정도 된다. 따라서 20번 가량의 점프가 이루어지는 거는 동일하다.

여기서 알 수 있는 건 점프 횟수 = 트리높이 라는 점이다. 성능을 올리려면 점프 횟수를 줄여야하고, 이는 곧 트리의 높이를 줄여야 한다는 뜻이다. 즉, 한 노드가 자식 노드를 많이 갖게 하면 되는 것이다. 여기서 B-tree가 나온다. 

 

 

2. B-tree 와 B+tree

B-tree

B-tree는 한 노드의 크기를 디스크 페이지 한 개에 맞춰서 키를 수백개씩 담는다. 즉 디스크를 한 번 읽으면 수백개의 키를 한번에 얻고, 그 안에서는 메모리상 비교만 하면 된다. 때문에 트리가 극적으로 얕아진다. 한 노드가 갖는 자식 개수가 많으니 높이가 낮아지는 것이다. 

 

또 다른 특징은 항상 균형을 유지한다는 것이다. B-tree의 B는 Binary가 아닌 Balanced 다. 

모든 리프 노드가 같은 깊이에 있어 어떤 키를 찾던 노드 수가 같다. 이를 유지하기 위해 노드가 꽉차면 노드를 둘로 쪼개고, 가운데 키를 부모로 올린다. 삭제의 경우 너무 비면 형제노드와 합치거나 빌려오기도 한다. (merge/borrow)

 

 

사실 DB에서 B-tree 인덱스라고 부르는 건 거의 B+tree 이다. 

 

B+tree

B+tree는 실제 데이터를 리프노드에만 두고, 중간 노드는 길 안내용 키만 갖는다. 중간 노드가 데이터 공간을 쓰지 않으니 갈래는 더 넓어지고 높이는 더 낮아지게 된다. 또, 리프노드끼리는 좌우로 연결되어있는 구조는 갖는다.

 

검색을 할 때 B+tree는 시작점을 찾고, 리프 사이의 연결을 따라 옆으로 읽는다. 매번 루트부터 내려갈 필요 없이 옆으로 스캔하니 순차 i/O에 가깝게 검색이 진행된다!

 

 

3. 클러스터드 인덱스 vs 세컨더리 인덱스

InnoDB(MySQL) 에서는 테이블 자체가 PK 기준 B+tree이고, 이를 클러스터드 인덱스라고 한다. 리프노드에는 행 전체가 들어있기 때문에, PK로 검색하는 경우 리프가 곧 데이터라 추가 점프가 거의 필요없다.

 

문제는 다른 칼럼으로 만든 인덱스인데, 이를 세컨더리 인덱스 (보조인덱스) 라고 한다. 보조 인덱스의 리프에는 행 데이터가 아닌 PK 값만 들어있기 때문에, 실제 데이터를 가져오려면 보조인덱스에서 PK를 얻고, 이 PK로 클러스터드 인덱스를 한 번 더 이용해야한다. 

 

참고로 PostgreSQL은 클러스터드 인덱스 개념이 없고 데이터는 힙에 따로 저장된다. 그리고 인덱스는 힙의 물리 위치를 가리킨다. 즉, PostgreSQL는 사실상 세컨더리처럼 동작하게 된다. 

 

 

이처럼 인덱스는 조회를 빠르게 해주지만, Insert, Update, Delete 가 일어날 때마다 갱신이 필요하기 때문에 느려질 수 있다. 인덱스를 생성할 때에는 Command와 Query의 트레이드오프를 항상 생각하며 필요한 것만 만들어야 한다!

---

이렇게 B-tree와 B+tree의 구조를 알아보았다. 다음 게시글은 복합인덱스에 대해 정리해볼 생각이다!