🟣 왜 트리를 넓혀야 했나
앞 장의 결론은 분명했다. 디스크에서는 노드를 하나 따라갈 때마다 접근이 한 번 들고, 그 횟수는 트리 높이가 결정한다. 이진 트리는 분기수가 2뿐이라 백만 건이면 높이가 스무 남짓이고, 그만큼 디스크에 손을 댄다. 높이를 줄이는 길은 하나다. 한 노드에서 갈래를 최대한 많이 뻗는 것이다.
마침 앞선 장에서 블록이라는 단위를 봤다. 디스크는 어차피 블록 단위로 읽으므로, 노드 하나를 블록 하나 크기로 채우면 그 안에 키를 수백 개까지 담을 수 있다. 노드 안에 키가 많으면 자식 갈래도 그만큼 많아진다. 갈래가 수백 개면 트리 높이는 log₂가 아니라 log(수백) 스케일로 뚝 떨어진다. 백만 건도 높이 서넛이면 닿는다. 이 발상을 정식 자료구조로 만든 것이 B트리다.
🟣 B트리: 블록에 맞춘 다분기 균형 트리
B트리는 차수(order) m으로 정의된다. 각 노드는 최대 m−1개의 키와 최대 m개의 자식을 가진다. 노드 안의 키들은 정렬돼 있고, 키 사이사이의 자식 포인터가 그 키 범위에 해당하는 하위 트리를 가리킨다. 예를 들어 키가 두 개면 자식은 셋이다. 첫째 키보다 작은 것, 두 키 사이의 것, 둘째 키보다 큰 것이다.
B트리의 균형 규칙은 AVL과 목적은 같되 방식이 다르다. AVL은 높이차를 회전으로 맞췄지만, B트리는 모든 리프가 항상 같은 깊이에 있도록 유지한다. 이 균형은 삽입과 삭제 때 노드를 나누고 합치며 지킨다.
삽입은 먼저 들어갈 리프를 찾아 키를 끼운다. 그 리프가 이미 꽉 차서 키가 m개가 되면 분할(split)한다. 노드를 반으로 가르고, 가운데 키를 부모로 밀어 올린다. 부모도 꽉 차 있으면 부모가 다시 분할되고, 이 연쇄가 루트까지 올라가면 루트가 쪼개지며 트리 높이가 한 단 늘어난다. B트리가 위로 자라는 순간은 오직 루트가 분할될 때뿐이라, 모든 리프의 깊이가 저절로 같게 유지된다.
삭제는 반대다. 키를 지운 노드의 키 수가 최소 기준(대략 절반) 밑으로 내려가는 언더플로가 나면, 형제에게서 키를 빌려 오는 재분배(redistribution)를 하거나, 형제와 하나로 합치는 병합(merge)을 한다. 병합이 연쇄되면 트리 높이가 한 단 줄기도 한다.
🟣 B+트리: 데이터를 리프로 몰고 리프를 잇는다
B트리를 데이터베이스 인덱스로 쓰다 보면 아쉬운 지점이 나온다. B트리는 내부 노드에도 실제 데이터(혹은 데이터를 가리키는 포인터)가 붙어 있다. 그래서 "20부터 70까지 전부"처럼 범위를 훑는 검색이 불편하다. 20을 찾은 뒤 다음 키로 넘어가려면 트리를 다시 오르내려야 한다. 정렬된 순서로 쭉 읽어 내려가는 자연스러운 통로가 없다.
B+트리는 이 문제를 두 가지 변형으로 푼다. 첫째, 실제 데이터는 리프 노드에만 둔다. 내부 노드는 어느 리프로 내려갈지 안내하는 라우팅용 키만 갖는다. 둘째, 모든 리프를 왼쪽에서 오른쪽으로 연결 리스트처럼 잇는다. 이 리프 연결이 B+트리의 핵심이다.
이 두 변형이 범위 검색을 극적으로 바꾼다. "20부터 70까지"를 찾으려면 트리를 한 번 내려가 20이 있는 리프에 닿은 뒤, 붉은 리프 연결을 따라 오른쪽으로 쭉 읽으면 끝이다. 트리를 다시 오르내릴 일이 없다. 범위 검색과 정렬된 순회, 그리고 ORDER BY가 전부 이 리프 연결 하나로 값싸진다.
삽입과 삭제의 성격도 B트리와 달라진다. B트리는 내부 노드에도 데이터가 있어 삭제할 키가 내부 노드에 걸리면 후행 키를 끌어와 대체하는 등 처리가 번거롭다. B+트리는 데이터가 리프에만 있으니 삭제는 항상 리프에서 일어난다. 내부 노드의 키는 안내판일 뿐이라, 리프에서 지운 키가 내부에 남아 있어도 라우팅에는 문제가 없다. 그만큼 삭제 로직이 단순하다. 대신 데이터가 리프에 몰려 내부 노드가 순수 인덱스가 되므로, 같은 블록 크기에 라우팅 키를 더 많이 담아 분기수가 오히려 커진다.
🟣 그래서 데이터베이스는 B+트리를 쓴다
여기서 CS 이론이 실무로 이어진다. 관계형 데이터베이스가 기본 인덱스로 B+트리 계열을 쓰는 이유가 이 장의 트레이드오프에 전부 담겨 있다.
우선 디스크 친화적이다. 노드를 데이터베이스 페이지(대개 블록에 대응) 하나에 맞추면, 노드를 읽는 일이 곧 페이지를 한 번 읽는 일이 된다. 분기수가 커서 백만, 천만 건도 높이 서넛이면 닿고, 그만큼 디스크 접근이 적다. 여기에 리프 연결 덕분에 BETWEEN, 범위 조회, ORDER BY, 페이지네이션 같은 순차 접근이 모두 값싸다. 등가 검색만 빠른 해시 인덱스가 범위 검색을 못 하는 것과 대비되는 지점이다. MySQL InnoDB가 기본 키를 B+트리 클러스터드 인덱스로 저장하고 리프에 실제 행 데이터를 나란히 두는 것도 이 성질을 활용한 설계다.
정리하면 B+트리는 앞의 세 장을 한 자리에 모은다. 1장의 블록으로 노드를 채워 디스크 접근을 줄이고, 2장의 균형 개념을 모든 리프를 같은 깊이로 유지하는 방식으로 지키며, 리프 연결로 순차 파일이 잘하던 정렬 순회까지 되찾는다. 순차 파일의 삽입 문제에서 시작한 이야기가 여기서 한 바퀴 돈다.
🟣 정리
- 디스크에서 높이를 줄이려면 분기수를 키워야 한다. B트리는 노드를 블록 크기로 채워 한 노드에 키를 수백 개까지 담고, 높이를 log(수백) 스케일로 낮춘다.
- B트리는 회전 대신 삽입 시 분할, 삭제 시 병합·재분배로 균형을 잡고, 모든 리프를 같은 깊이로 유지한다. 트리는 루트가 분할될 때만 위로 자란다.
- B+트리는 실제 데이터를 리프에만 두고 모든 리프를 연결 리스트로 잇는다. 이 리프 연결이 범위 검색과 정렬 순회를 값싸게 만든다.
- 데이터가 리프에만 있어 삭제가 리프에서만 일어나므로, B+트리의 삭제 로직이 B트리보다 단순하고 내부 노드의 분기수는 더 커진다.
- 데이터베이스가 B+트리를 인덱스로 쓰는 이유는 디스크 접근 최소화와 범위 검색 지원이라는 두 요구를 동시에 만족하기 때문이다.
면접에서 이 주제는 깊이 사다리가 길다. "B트리를 쓴다"에서 멈추지 말고, B트리와 B+트리의 차이, 리프 연결이 왜 범위 검색에 결정적인지, InnoDB의 클러스터드 인덱스와 세컨더리 인덱스가 리프에 무엇을 담는지까지 내려갈 수 있어야 한 주제로 대화를 오래 끌고 갈 수 있다.
다음 장에서는 이 모든 트리가 공유하는 한 가지 전제, 즉 키가 한 축으로 정렬된다는 가정이 깨지는 상황을 본다. 위치처럼 여러 축을 동시에 다뤄야 하는 다차원 인덱스, k-d 트리가 그 자리를 채운다.