B트리와 B+트리

개념 정의

B트리는 자식 수가 정해진 범위에서 변하며 키를 정렬 상태로 유지하는 균형 다진 탐색 트리다.

B+트리는 B트리를 변형한 구조로, 키만 내부 노드에 두고 데이터 포인터는 리프에만 둔다.

두 구조는 같은 균형 다진 트리지만 데이터를 두는 위치가 다르다. 이 차이가 핵심이다.

B+트리 구조

B+트리의 루트와 내부 노드는 탐색용 키만 가진다. 데이터는 가장 아래 단말 노드에만 있다.

단말 노드는 연결 리스트로 이어져 있어 범위 검색을 순서대로 따라갈 수 있다.

차수 m은 한 노드가 가질 수 있는 최대 자식 수다. 최소 채움률은 구현 기준으로 정한다.

삽입 절차

삽입은 루트에서 시작해 키가 들어갈 리프를 찾고, 정렬 순서대로 키를 넣는 것이다.

키 수가 최대 키 수를 넘으면 노드를 둘로 나누고 중간 키를 부모로 올려 보낸다.

부모도 넘치면 같은 과정을 반복한다. 루트까지 분할되면 새 루트가 생겨 높이가 1 늘어난다.

B+트리는 키를 복사해 부모에 올리고, B트리는 중간 키를 이동시킨다.

삭제 절차

삭제한 뒤에는 노드의 키 수가 최소 기준 이상인지 먼저 확인한다.

미달이면 형제 노드에 여분 키가 있을 때 재분배로 키를 빌려온다.

형제에도 여분이 없으면 형제와 병합하고, 부모에서 키 하나를 내린다.

병합이 루트까지 전파되어 루트 키가 0이 되면 트리 높이가 1 줄어든다.

두 구조 비교

두 구조를 같은 기준으로 비교하면 데이터를 두는 위치가 가장 큰 차이다.

B+트리는 키만 내부 노드에 두어 팬아웃이 커지고 트리 높이가 낮아진다.

B트리는 범위 검색에서 트리를 여러 번 오르내려야 한다. B+트리는 리프를 따라가면 된다.

정리

B트리는 모든 노드에 데이터가 있고, B+트리는 데이터를 리프에만 둔다.

삽입은 분할, 삭제는 재분배나 병합으로 노드 범위를 맞춘다.

검색·삽입·삭제 모두 O(log n)이다. 범위 검색이 잦은 인덱스에는 B+트리가 주로 쓰인다.