422. 인덱스 B+Tree 리프 노드 순차 연결

⚠️ 이 문서는 "1억 명의 회원 중에서 20대(20살~29살)를 가장 빨리 찾는 방법은 무엇일까?"라는 질문에 대해, 일반적인 이진 트리(Binary Tree)의 한계를 극복하고 **현대 관계형 데이터베이스의 99%가 채택하고 있는 가장 완벽한 인덱스 구조인 'B+Tree'**를 다룹니다.

핵심 인사이트 (3줄 요약)

본질: B+Tree는 데이터를 나무(Tree) 모양으로 뒤집어 놓은 구조다. 일반 B-Tree와 달리, 가장 아래에 있는 나뭇잎(리프 노드)에만 실제 데이터(또는 주소)를 저장하는 것이 가장 큰 특징이다.

가치 (범위 검색 최적화): 리프 노드들끼리 서로 **기차처럼 연결(Linked List)**되어 있어서, BETWEEN 이나 > 같은 범위 검색을 할 때 처음부터 다시 나무를 탈 필요 없이 기차를 타고 옆 칸으로 쭉 넘어가면 된다.

구조: 검색을 안내하는 표지판 역할의 **'브랜치 노드'**와, 실제 데이터가 담겨 기차처럼 연결된 **'리프 노드'**로 완벽하게 역할이 분리되어 있다.

Ⅰ. 개요: 책갈피와 목차 (Context & Necessity)

데이터베이스에서 인덱스(Index)는 두꺼운 전공서적 맨 뒤에 있는 **'찾아보기(색인)'**와 같다. "데이터베이스"라는 단어가 350페이지에 있다는 걸 알면, 처음부터 책을 다 넘길(Full Scan) 필요 없이 350페이지로 바로 점프하면 된다.

문제는 이 '찾아보기' 자체도 데이터가 1억 건이면 엄청나게 크다는 것이다. 찾아보기 안에서 내가 원하는 단어를 빨리 찾기 위해 수학자들이 만들어낸 자료구조가 바로 **B-Tree (Balanced Tree)**다. B-Tree는 어떤 데이터를 찾든 무조건 3~4번 만에 찾아낼 수 있게 트리의 균형을 항상 1:1로 맞춘다. 하지만 일반 B-Tree는 치명적인 단점이 하나 있었다.

📢 섹션 요약 비유: 일반 B-Tree가 **'단어 1개를 찾기'**에 최적화된 구조라면, B+Tree는 **'10번부터 20번까지 통째로 찾기(범위 검색)'**를 위해 나뭇잎들을 끈(Linked List)으로 다 묶어버린 업그레이드 버전입니다.

Ⅱ. 일반 B-Tree의 한계와 B+Tree의 등장

1. 일반 B-Tree의 문제점 (범위 검색 쥐약)

20살부터 25살까지 찾고 싶다.
뿌리에서 출발해 20살을 찾았다. (성공)
21살을 찾으려면? 다시 뿌리(Root)로 돌아가서 21살로 가는 길을 새로 찾아야 한다.
22살을 찾으려면? 또 뿌리로 돌아가야 한다. 미치도록 비효율적이다.

2. B+Tree의 혁명 (리프 노드 순차 연결) ★

B+Tree는 **가장 아래층(Leaf Node)**에만 진짜 데이터를 몰아넣었다.
그리고 이 리프 노드들끼리 서로 손을 잡게 만들었다. (Linked List)
20살을 찾았다. 21살을 찾기 위해 뿌리로 돌아가지 않는다. 그냥 옆 사람(21살) 손을 잡고 넘어간다. 22살? 또 옆으로 넘어간다.
관계형 DB에서 가장 많이 쓰이는 쿼리인 WHERE age BETWEEN 20 AND 25가 0.01초 만에 실행되는 비밀이 바로 이 **'리프 노드 순차 연결'**에 있다.

Ⅲ. B+Tree의 3계층 구조

B+Tree는 깊이(Depth)가 깊어지는 것을 극도로 혐오한다. 보통 1억 건의 데이터도 3~4층(Depth 3~4) 안에서 다 끝난다.

루트 노드 (Root Node): 트리의 꼭대기. "100 이하는 왼쪽으로 가, 100 이상은 오른쪽으로 가!"
브랜치 노드 (Branch Node): 중간 표지판들. 오직 '길 안내'용 숫자만 들어있고, 실제 데이터는 절대 안 들고 있다.
리프 노드 (Leaf Node): 트리의 바닥. 진짜 데이터(또는 데이터가 있는 디스크 주소인 ROWID)가 들어있다. 여기서부터는 옆방으로 마음껏 이동할 수 있다.

┌──────────────────────────────────────────────────────────────┐
│           B+Tree 인덱스의 리프 노드 연결망 시각화                │
├──────────────────────────────────────────────────────────────┤
│                                                              │
│           [ 👑 Root: 50을 기준으로 ]                          │
│            /                     \                           │
│     (50 미만)                    (50 이상)                     │
│        ▼                            ▼                        │
│ [ 🎋 Branch: 30 기준 ]        [ 🎋 Branch: 70 기준 ]         │
│    /       \                      /       \                  │
│   ▼         ▼                    ▼         ▼                 │
│ [🍃 10,20] ──▶ [🍃 30,40] ──▶ [🍃 50,60] ──▶ [🍃 70,80]        │
│                                                              │
│ ★ 검색 예시: "20부터 60까지 다 가져와!" (BETWEEN 20 AND 60)         │
│   1. 루트 -> 브랜치 -> 🍃20이 있는 리프 노드로 착지 (수직 탐색)            │
│   2. 뿌리로 안 돌아가고, 화살표(▶)를 타고 오른쪽으로 계속 전진! (수평 탐색)  │
│   3. 60을 만날 때까지 그냥 옆방 문만 열면 됨. 속도 최고! 🚀              │
└──────────────────────────────────────────────────────────────┘

Ⅳ. 결론

"DB의 심장은 B+Tree다." MySQL의 InnoDB, Oracle, PostgreSQL 등 우리가 아는 거의 모든 RDBMS는 인덱스를 만들 때 CREATE INDEX ... USING BTREE를 기본값으로 사용한다. (이름은 B-Tree지만 내부적으로는 모두 업그레이드된 B+Tree를 쓴다). 메모리에 올려두고 쓰는 캐시(Hash)나 빅데이터 쓰기 전용 엔진(LSM-Tree - 377번 문서)이 유행하는 시대에도, '수시로 변경되는 데이터'와 '범위 검색'이라는 두 마리 토끼를 동시에 잡는 자료구조는 B+Tree가 유일무이하다.

📌 관련 개념 맵

관련 인덱스: Clustered Index (424번), Non-Clustered Index (423번)
대안 자료구조: Hash Index (정확히 일치하는 = 검색만 가능, 범위 검색 불가)
발생하는 문제: 인덱스 단편화 (데이터가 자꾸 끼어들면 노드가 쪼개지며 빈 공간이 생기는 Page Split 현상 발생)

👶 어린이를 위한 3줄 비유 설명

일반 B-Tree는 아파트 1층부터 10층까지 배달을 할 때, 1층 배달하고 다시 1층 로비(뿌리)로 내려갔다가, 2층 배달하고 또 1층 로비로 내려가는 바보 같은 배달부예요.
B+Tree는 꼭대기 층(리프 노드)에 올라가면, 옥상끼리 다 구름다리(연결선)로 연결되어 있는 멋진 아파트예요.
그래서 101동 옥상에 한 번만 올라가면, 102동, 103동으로 1층에 안 내려가고 바로바로 건너갈 수 있어서 배달(범위 검색)이 엄청 빨라요!