인덱스 - DB 성능 최적화의 핵심

• 인덱스와 실행 계획은 DB 성능의 80%를 결정짓는 핵심 분야
• 인덱스의 가장 기본이 되는 B+Tree 구조부터 시작해보자.

B+Tree란 무엇인가?

• B+Tree는 이진 트리(Binary Tree)를 확장하여 하다의 노드가 가질 수 있는 자식 노드의 개수를 늘린 B-Tree의 변형 구조이다
• 핵심 특징:
  • 모든 키 값은 Leaf Node에만 존재:
    • Root와 Internal 노드는 데이터의 위치를 안내하는 이정표 역할만 하며, 실제 데이터는 가장 하위인 Leaf 노드에만 저장된다.
  • Leaf Node 간의 Linked List:
    • 모든 Leaf 노드는 서로 연결 리스트(Linked List)로 이어져있어 순차 검색(Full Scan)이나 범위 검색(Range Scan)에 최적화되어 있다
  • 데이터 정렬:
    • 모든 노드 내의 데이터는 정렬된 상태를 유지한다.

왜 B-Tree가 아니라 B+Tree인가?

• 일반적인 B-Tree도 훌륭한 자료구조지만, DB 인덱스 관점에서는 B+Tree가 가지는 압도적인 장점들이 있다.

• 효율적인 범위 검색(Range Scan)

  • B-Tree : 특정 범위(예: WHERE age > 20)를 찾으려면 트리 전체를 중위 순회(In-order-traversal)하며 위아래로 계속 이동해야 한다.
  • B+Tree : 시작점인 Leaf 노드 하나만 찾으면, 그 이후부터는 연결 리스트를 따라 옆으로 쭉 읽기만 하면 된다.
    • 인덱스 풀 스캔이나 범위 검색 속도가 훨씬 빠르다.

• 더 많은 키 저장 가능(I/O 효율성)

  • B-Tree : 각 노드가 데이터까지 직접 들고 있다.
  • B+Tree : 중간 노드에는 데이터 없이 인덱스 키만 담긴다.
  • 결과 :
    • 하나의 페이지 (보통 16KB)에 더 많은 키를 담을 수 있다.
    • 이는 트리의 높이를 낮게 유지해주며, 디스크 I/O 횟수를 획기적으로 줄여준다.
    • (보통 3~4레벨이면 수천만 건의 데이터를 커버한다.)

• 캐시 히트율 상승

  • 중간 노드의 크기가 작기 때문에 메모리(InnoDB Buffer Pool)에 더 많은 인덱스 노드를 캐싱할 수 있어, 실제 디스크에 접근하는 빈도가 낮아진다.

그렇다면 B+Tree에 어떻게 저장되는지 살펴보자.

• 이해를 돕기 위해, 간단한 사용자(User) 테이블을 예시로 들어 B+Tree가 인덱스 키를 어떻게 배치하고 데이터를 저장하는지 시각화 해보자.

예시 테이블 (MySQL InnoDB 기준)

CREATE TABLE users (
    user_id INT PRIMARY KEY, -- 클러스터형 인덱스 (B+Tree)
    name VARCHAR(20),
    age INT
);

• 샘플 데이터 (PK 기준 정렬): 10, 15, 20, 25, 30, 35, 40 (총 7개의 레코드)

B+Tree 인덱스 시각화 (Clustered Index)

• InnoDB에서 PK 인덱스는 데이터 그 자체를 들고 있는 클러스터형 인덱스이다.

[ Root Node (Level 0) ]
       [ 25 |  ]  <-- 25를 기준으로 길을 나눔
      /        \
     /          \
[ Internal Node (Level 1) ]             [ Internal Node (Level 1) ]
    [ 15 | 20 ]                             [ 35 | 40 ]
   /     |     \                           /     |     \
  /      |      \                         /      |      \
[Leaf] [Leaf] [Leaf] <--- 연결 리스트 ---> [Leaf] [Leaf] [Leaf] (Level 2)
  |      |      |                         |      |      |
 [10]   [15]   [20]                      [25]   [30]   [35]   [40]
Record Record Record                   Record Record Record Record

상세 분석

• Root & Internal Nodes (이정표):
  • 여기에는 실제 사용자 이름이나 나이 데이터가 없다.
  • 오직 PK(user_id)와 자식 노드의 주소만 기록된다.
  • 예: user_id = 22를 찾는다면,
    • Root에서 "25보다 작네?" -> 왼쪽 Internal 노드로 이동
    • "15, 20보다 크네?" -> 세 번째 Leaf 노드로 이동 순으로 탐색한다.
• Leaf Nodes (실제 데이터):
  • B+Tree의 핵심
  • 여기에는 user_id뿐만 아니라 해당 행의 모든 데이터(name, age등)가 함꼐 저장된다.
• Horizontal Linked List(옆으로 그어진 화살표)
  • 모든 Leaf 노드는 이전 / 다음 노드의 주소를 알고 있다
  • WHERE user_id BETWEEN 15 AND 35라는 쿼리가 들어오면, 트리 타고 15를 찾은 뒤
  • 그때부터는 트리를 다시 올라가지 않고 옆으로만 쭉 읽어서 35까지 가져온다. (매우 빠름!)

왜 이렇게 저장할까요?

• 포인터의 최소화:
  • 만약 위 그림이 B-Tree였다면, Root 노드인 25에도 name, age 데이터가 붙어 있었을 것이다.
  • 그러면 노드 하나(페이지)에 담을 수 있는 PK 개수가 줄어들어 트리가 위로 길어진다. (높이가 높아짐)
• Disk I/O의 법칙:
  • DB 성능의 병목은 보통 디스크 읽기이다.
  • B+Tree는 중간에 데이터가 없어서 한 페이지에 수백 개의 PK를 담을 수 있고
  • 덕분에 아무리 데이터가 많아도 보통 3~4번의 점프(I/O)면 원하는 데이터에 도달한다.

그렇다면 데이터 삽입/삭제될 때 어떤 일이 벌어질까?

데이터 삽입 시 : 노드 분할 (Node Split)

B+Tree는 정렬 상태를 유지해야 하며, 각 노드(Page)의 용량은 제한적이다.
(MySQL은 기본 16KB)

• 빈 공간이 있을 때:
  • 정렬 순서에 맞춰 ㄹ해당 Leaf 노드에 데이터를 넣고 끝난다.
• 노드가 가득 찼을 때(Split):
  • 해당 Leaf 노드를 두 개로 쪼갠다.
  • 중간값을 부모 노드로 올린다.
  • 만약 부모 노드도 가득 찼다면, Root 노드까지 이 현상이 전이될 수 있다.
  • 이 과정에서 새로운 페이지를 할당받고 데이터를 재배치하므로 비용이 많이 든다

데이터 삭제 시 : 노드 병합 (Node Merge / Rebalance)

삭제는 삽입의 반대 과정

• 데이터 삭제:
  • 해당 키를 삭제 한다.
  • B+Tree는 실제 데이터가 Leaf에만 있으므로 항상 Leaf에서 삭제 발생
• 언더플로우(Underflow):
  • 삭제 후 노드에 남은 데이터가 너무 적으면, (보통 50% 미만) 인덱스 구조가 비효율적으로 변한다
• 병합 또는 재배치:
  • 옆 노드에서 데이터를 빌려오거나
  • 옆 노드와 하나로 합친다(Merge)
  • 이 과정에서도 부모 노드의 키가 수정되거나 삭제될 수 있다.

페이지(Page)의 의미

• MySQL InnoDB 엔진에서 페이지(Page)는 디스크와 메모리(Buffer Pool) 사이에서 데이터를 주고받는 최소 작업 단위이며, 기본 설정값이 바로 16KB이다.
• 이 페이지의 크기가 인덱스 구조와 성능에 미치는 영향은 결정적이다.

노드(Node) = 페이지(Page)

• B+Tree 시각화 자료에서 보았던 '네모 박스' 하나가 곧 16KB짜리 페이지 하나라고 생각하면 된다.
  • Internal 노드 한 페이지:
    • 자식 노드들을 가리키는 이정표 역할
  • Leaf 노드 한 페이지:
    • 실제 데이터(Record)들이 담겨 있다.

페이지 크기가 인덱스에 미치는 영향

• 트리의 높이

  • 페이지 크기가 고정되어 있기 떄문에, 인덱스 키(Column)의 사이즈가 작을수록 한 페이지에 더 많은 이정표를 담을 수 있다.
    • 만약 PK가 BIGINT(8바이트)라면, 페이지 주소값 등을 포함해도 한 페이지에 약 1,000개 이상의 자식 노드 주소를 저장할 수 있다.
    • 이 경우, 단 3개 층(Root - Internal - Leaf)만으로도 1,000 _ 1,000 _ 1000 = 10억 개의 레코드를 관리할 수 있다.
    • 결론: 페이지 크기 내에 키를 많이 채울수록 트리가 낮아지고, 데이터를 찾기 위한 디스크 I/O 횟수가 줄어들어 성능이 좋아진다.

• 페이지 분할(Page Split)의 기준

  • 데이터를 INSERT하다가 해당 페이지의 여유 공간이 16KB를 넘어서려고 하면, 데이터베이스는 페이지를 두 개(8KB, 8KB)로 나눈다
    • 문제점: 페이지 분할이 일어나면 새로운 페이지를 할당받아야 하고, 상위 노드의 정보도 갱신해야 한다.
    • 이 작업 동안 해당 인덱스 범위에 락(Lock)이 걸릴 수 있어 동시성이 떨어진다.

• 단편화(Fragmentation)

  • 데이터를 무작위로 삭제하거나 삽입하면 페이지 내부에 16KB를 다 채우지 못한 빈 공간이 많이 생긴다
  • 공간은 차지하는데 실제 데이터는 적은 상태가 되어, 풀 스캔시 읽어야할 페이지 수가 많아져 성능이 저하된다.
  • 이 때 OPTIMIZE TABLE로 페이지를 재정렬할 수 있다.