B 트리와 B+ 트리 (B-Tree & B+ Tree)

B 트리(B-Tree)는 한 노드에 여러 개의 키와 자식을 담아 트리의 높이를 극단적으로 낮춘 균형 다진 탐색 트리이고, B+ 트리(B+ Tree)는 모든 데이터를 리프(leaf)에 모으고 리프끼리 연결 리스트로 이은 그 변형이다. 두 구조는 디스크처럼 블록 단위로 읽는 저장 장치에서 접근 횟수를 최소화하도록 설계되어, 관계형 데이터베이스의 인덱스(index)와 파일 시스템의 표준 자료구조로 쓰인다. 특히 B+ 트리는 범위 검색에 강해 MySQL의 InnoDB를 비롯한 대부분의 데이터베이스 인덱스가 채택하고 있다.

왜 이진 트리로는 부족한가

메모리 위에서는 레드 블랙 트리(Red-Black Tree) 같은 이진 탐색 트리로 충분하다. 그러나 디스크는 다르다. 디스크와 SSD는 데이터를 페이지(page)라는 블록 단위(보통 수 킬로바이트)로 읽어오며, 한 번의 입출력(I/O) 비용이 메모리 접근보다 압도적으로 크다. 이진 트리는 노드 하나에 키가 하나뿐이라 노드를 옮길 때마다 I/O가 발생할 수 있고, 데이터 백만 건이면 높이가 20에 달해 탐색 한 번에 디스크를 스무 번 읽어야 할 수도 있다.

B 트리의 발상은 단순하다. 한 번 읽어 온 페이지를 최대한 활용하도록, 노드 하나를 페이지 크기에 맞추고 그 안에 키를 수백 개씩 담는 것이다. 자식이 수백 갈래로 갈라지면 백만 건도 높이 3에서 4 안에 들어오고, 디스크 접근이 그만큼으로 줄어든다.

B 트리의 구조와 동작

차수 m의 B 트리에서 각 노드는 최대 m-1개의 키와 m개의 자식을 갖고, 루트를 제외한 노드는 최소 절반가량 차 있어야 한다. 노드 안의 키는 정렬되어 있으며, 키 사이사이의 자식 포인터가 해당 구간의 값들을 담은 부분 트리를 가리킨다. 모든 리프는 같은 깊이에 있어 트리가 항상 완전한 균형을 이룬다.

삽입은 리프에서 이루어지며, 노드가 가득 차면 가운데 키를 부모로 올려보내고 노드를 둘로 쪼갠다(분할, split). 분할이 루트까지 전파되면 트리 높이가 1 늘어난다. 삭제 시 노드가 최소 키 수 아래로 떨어지면 형제에게서 키를 빌리거나(재분배) 형제와 합친다(병합, merge). 이 규칙 덕분에 트리는 스스로 균형을 유지하고 모든 연산이 O(log n)으로 보장된다.