B-트리 (B-Tree)
쉽게 풀면
도서관에서 책을 찾는 상황을 생각해봅시다. 책장 한 칸에 책을 딱 한 권씩만 꽂아두면 원하는 책까지 가는 통로가 매우 길어집니다. 반대로 한 칸에 여러 권을 순서대로 나란히 꽂아두면, 통로를 훨씬 적게 오가고도 원하는 책 근처에 도착할 수 있습니다. B-트리는 바로 이 아이디어를 자료구조에 적용한 것입니다. 이진탐색트리처럼 한 노드에 값을 하나만 두지 않고, 한 노드에 여러 개의 값과 여러 개의 자식 가지를 두어 트리를 옆으로 넓고 낮게 만듭니다. 그 결과 원하는 값을 찾을 때 노드(디스크 블록)를 방문하는 횟수 자체가 크게 줄어듭니다.
왜 중요한가
B-트리는 메모리보다 훨씬 느린 디스크나 SSD 같은 보조기억장치를 다루는 시스템에서 성능을 좌우하는 핵심 자료구조입니다. 관계형 데이터베이스의 인덱스, 파일시스템의 디렉터리 구조, 대용량 키-값 저장소 등 저장장치 접근이 병목이 되는 거의 모든 시스템 설계 논문에서 기본 비교 대상 혹은 기반 구조로 등장합니다. 그래서 새로운 인덱스 구조나 저장 엔진을 제안하는 논문은 대체로 B-트리 계열과의 성능 비교를 통해 자신의 기여를 설명하는 경우가 많습니다. 이런 배경 때문에 데이터베이스·운영체제·분산시스템 분야 논문을 읽으려면 B-트리의 동작 원리를 이해하고 있는 것이 사실상 전제 지식으로 취급됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 데이터가 아무리 많아져도(n이 커져도) 한 노드가 저장할 수 있는 값의 개수(m)가 많을수록 트리의 높이가 낮게 유지되어, 디스크를 오가는 횟수가 크게 늘지 않는다는 뜻입니다. 데이터베이스 인덱스, 파일시스템 논문에서 핵심 자료구조로 자주 인용됩니다.
파일시스템 논문에서는 디렉터리 안에 파일이 아주 많아지더라도 탐색 속도가 크게 나빠지지 않아야 한다는 요구가 있는데, 이때 B-트리 계열 구조가 자주 채택됩니다. 리스트나 단순 해시 구조 대신 B-트리를 쓰면 파일 개수가 늘어나도 탐색 시간이 완만하게 늘어난다는 점을 강조하는 문장입니다.
디스크뿐 아니라 CPU 캐시와 메인 메모리 사이의 접근 속도 차이를 줄이는 데도 B-트리의 아이디어가 응용된다는 내용입니다. 저장장치의 종류가 디스크에서 메모리 계층으로 바뀌어도, 한 노드에 여러 값을 묶어 접근 횟수를 줄인다는 B-트리의 기본 발상은 그대로 재사용됩니다.
조금 더 깊게 보면
논문을 읽을 때는 B-트리 자체보다 그 변형인 B+트리를 다루는 경우가 훨씬 많다는 점을 알아두면 도움이 됩니다. B+트리는 실제 데이터(레코드나 포인터)를 리프 노드에만 모아 저장하고, 리프 노드들을 연결 리스트로 이어 범위 검색(range query)을 빠르게 처리할 수 있도록 만든 구조입니다. 또한 B-트리의 성능을 이야기할 때는 트리의 차수(order, 한 노드가 가질 수 있는 자식 수의 최대값)와 트리 높이의 관계, 그리고 삽입·삭제 시 노드를 분할(split)하거나 병합(merge)해 균형을 유지하는 과정을 함께 살펴보면 논문의 설명을 더 정확히 이해할 수 있습니다. 성능을 비교하는 논문에서는 대체로 디스크 I/O 횟수나 트리 높이를 이론적 지표로 제시하고, 여기에 실제 캐시 적중률이나 처리량 같은 실험 결과를 곁들이는 방식을 씁니다.
주의할 점
B-트리는 값을 트리 전체(내부 노드와 리프 노드)에 나눠 저장하지만, 실제 데이터베이스 인덱스에 널리 쓰이는 것은 값을 오직 리프 노드에만 모아두고 리프끼리 연결 리스트로 이어놓은 변형인 B+트리입니다. 또한 B-트리는 메모리 내 검색 속도보다 저장장치 접근 횟수를 줄이는 데 초점을 둔다는 점에서, 메모리 안에서의 빠른 비교 자체가 목적인 이진탐색트리와는 설계 목적이 다릅니다.