[CS] 데이터베이스 인덱스 자료구조는 왜 B-Tree 계열일까

1. 인덱스의 기본 개념

인덱스는 테이블의 특정 열에 대해 정렬된 데이터 구조이다.
인덱스를 사용하면 전체 데이터를 스캔하지 않고도 원하는 데이터에 빠르게 접근할 수 있다.

인덱스의 장점

• 검색 속도 향상
• 정렬 및 그룹화 연산 최적화
• 데이터 무결성 보장 (유니크 인덱스 사용 시)

인덱스 단점

• 추가 저장 공간 필요
• 데이터 변경 시 인덱스 또한 업데이트로 인한 쓰기 성능 저하

2. 인덱스 설정 시 무엇을 고려

카디널리티 (Cardinality)

카디널리티는 특정 데이터 집합의 유니크한 값의 개수를 의미
이때는 높은 카디널리티를 가진 열이 인덱스에 더 적합

예를 들어:

• 높은 카디널리티: 주민등록번호, 이메일 주소
• 낮은 카디널리티: 성별, 학년

선택도 (Selectivity)

선택도는 전체 데이터 중에서 특정 조건을 만족하는 데이터의 비율
즉, 낮은 선택도(즉, 더 특정한 값)를 가진 열이 인덱스에 적합합니다.

예를 들어:

• 낮은 선택도 (좋음): WHERE 생년월일 = '1990-01-01'
• 높은 선택도 (나쁨): WHERE 성별 = '남성'

일반적으로 카디널리티가 높고 선택도가 낮을수록 인덱스 효율이 높다.

3. 그럼 왜 B-Tree계열을 인덱스 자료구조로 사용할까?

3.1 해시 테이블

해시 테이블은 키-값 쌍을 저장하는 자료구조로, 평균적으로 O(1)의 시간 복잡도로 탐색이 가능하다.

즉, 탐색 속도가 빠르지만 왜 인덱스 자료구조로 사용하지 않을까?

바로 해시 테이블은 범위 탐색에는 유리하지만

데이터베이스에서 주로 사용하는 범위 탐색에는 적합하지 않다.

3.2 이진 트리

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조이다.

이진 트리는 탐색 시 최악이 경우 시간복잡도가 O(N)이다.

그렇다면 생각할 수 있는 게 최악의 경우도 시간복잡도가 O(logN)인 AVL트리가 있다.

3.3 AVL 트리

AVL 트리는 자가 균형 이진 탐색 트리로, 항상 O(log N)의 시간 복잡도를 보장한다.

MySQL에서 인덱스 자료구조로 사용하는 B-Tree의 경우에도 최악의 경우 시간복잡도가 O(logN)이다.

그렇다면 왜 AVL 트리는 인덱스의 자료구조로 사용하지 않는 것일까?

바로, B-Tree는 2개 이상의 자식 노드를 가질 수 있지만
AVL트리는 최대 2개의 자식 노드 밖에 가지지 못 한다.

즉, AVL트리는 B-Tree에 비해 트리의 높이가 높아 디스크 접근 횟수가 많다.

따라서 최악의 경우 탐색 시 시간복잡도는 O(logN)으로 동일하지만
AVL트리보다 B-Tree의 성능이 더 좋다.

3.4 레드-블랙 트리 (RB-Tree)

레드-블랙 트리는 AVL와 동일한 이진 균형 트리이다.

AVL은 왼쪽 서브트리와 오른쪽 서브 트리간의 높이차가 최대 1이여야 하는 엄격한 규칙을 가지고 있는데

레드-블랙 트리는 이 보다는 덜 엄격한 균형 규칙을 가진다.

따라서 AVL 트리보다도 탐색 성능이 떨어진다.

3.5 B-Tree

B-Tree는 각 노드가 여러 개의 키와 자식을 가질 수 있다.
따라서 트리의 높이가 낮아 디스크 접근 횟수를 줄일 수 있다.

즉, 최악의 경우 탐색 성능은 O(logN)으로 다른 자료구조와 동일하지 디스크 접근 횟수가 적어 성능이 더 좋다.

3.6 B+Tree

B+Tree와 B-Tree의 차이점은 다음과 같다.

• 리프 노드를 제외하고는 값을 어떤 노드에도 저장하고 있지 않는다.
  따라서 노드가 더 많은 key를 가질 수 있어 트리의 높이를 낮춘다.
  결과적으로 디스크에 접근하는 횟수를 줄어들게 하여 성능상 더 좋다.
• 리프 노드들이 연결 리스트로 연결되어 있다.
  이는 범위 탐색에 효율적이다.
  cf) B-Tree의 경우 풀 스캔 시 모든 노드를 탐색해야 하지만 B+Tree의 경우 리프노드만 탐색하면 된다.
  

이러한 이유로 인덱스 자료구조에서는 B-Tree계열을 사용하고 있고
특히나 MySQL의 InnoDB 스토리지 엔진에서는 B+Tree를 사용하고 있다.