B+Tree

B-Tree

B-Tree는 하나의 노드에 여러 데이터가 저장될 수 있다. 따라서 같은 노드 내에서 데이터를 탐색할 때는 포인터를 따라가는 방식이 아니라, 디스크(또는 메모리)에 연속적으로 저장된 인덱스를 순차적으로 확인하는 방식으로 탐색이 이루어진다. 이때, 특정 노드의 데이터(key)가 K개라면, 자식 노드의 개수는 K+1개여야 한다.

특징

예를 들어, 위의 B-Tree 구조에서 33이라는 값이 존재하는지 확인한다고 가정해보자. 루트 노드에는 20, 40이 저장되어 있는 상태이기 때문에 루트 노드에는 해당 값이 존재하지 않아 자식 노드를 가리키는 포인터의 존재 유무를 확인한다. 20과 40 사이의 범위에 해당하는 자식 노드를 가리키는 포인터가 있는 것을 확인했다면, 포인터를 따라가 자식 노드에 도달한다. 자식 노드에 존재하는 30, 33 값들은 디스크 상에서 순차적으로 배치되어 있기 때문에 빠르게 탐색할 수 있다.

B-Tree는 트리가 편향되지 않도록 항상 균형을 유지한다. 즉, 모든 리프 노드들은 같은 레벨에 존재해야하는 Balanced Tree이다. 때문에 최악의 경우에도 O(logN)의 시간 복잡도가 보장된다.

B+ Tree

B+ Tree는 인덱스 구현에 널리 사용되는 자료구조로, 기존 B-Tree를 확장한 형태이다. 

B+ Tree는 데이터베이스 인덱스 구현에 널리 사용되는 자료구조로, 기존 B-Tree를 확장한 형태이다. 가장 큰 특징은 모든 실제 데이터가 리프 노드에만 저장된다는 점이다.  반면, 리프 코드가 아닌 내부 노드(Interval Node)에는 데이터를 찾기 위한 키(Key)와 자식 노드를 가리키는 포인터만 저장된다. 이러한 구조 덕분에 메모리 사용 효율이 높으며, 또한 리프 노드들이 연결 리스트로 서로 연결되어 있기 때문에 범위 검색 성능이 우수하다. 다만, 탐색을 위해서는 무조건 리프노드까지 내려가야한다는 단점도 존재한다.

삽입

B+ Tree에서 데이터 삽입은 항상 리프 노드에서 이루어지며, 삽입 시 노드는 항상 정렬된 상태를 유지한다. 만약 삽입으로 인해 노드가 넘치게 되면, 가운데 Key를 기준으로 노드를 좌우로 분할하고, 가운데 Key는 부모 노드로 승격된다.

예를 들어 값 45를 삽입한다고 가정해 보자. 루트 노드에 15, 25가 저장되어 있다면, 45는 이보다 큰 값이므로 가장 오른쪽 자식 노드로 내려간다. 그러나 이 노드에 삽입할 경우 노드가 넘치게 되므로, 가운데 Key인 35를 부모 노드로 승격시킨다. 이때 35가 루트로 올라가면서 루트 노드 역시 넘치게 되고, 다시 가운데 Key인 25가 승격된다. 이처럼 삽입 과정에서는 연쇄적인 분할과 승격이 발생할 수 있으며, 이를 통해 트리의 균형이 유지된다.

삭제

리프노드에만 존재하며 재조정도 필요 없는 경우

리프 노드에 존재하는 값인 40을 삭제한 후에도 최소 개수 조건을 만족하므로 재조정이 일어나지 않는다.

리포노드에만 존재하고 재조정이 필요한 경우

B+ Tree에서 값을 삭제할 때는 항상 최소 개수 조건을 만족해야 한다. 그러나 예를 들어 값 5를 삭제하는 순간 해당 노드가 최소 개수 조건을 만족하지 못한다면 트리의 균형을 유지하기 위해 재조정이 이루어진다. 각 노드가 가져야 하는 최소 Key의 개수는, 노드의 최대 자식 수를 M이라고 했을 때 ⌈M/2⌉ - 1로 정의된다.

재조정 과정은 크게 두 단계로 나뉜다. 먼저, 키 수가 여유 있는 형제 노드로부터 도움을 받는다. 일반적으로 왼쪽 형제 노드부터 확인하여 여유 키가 있으면 하나를 빌려오고, 그렇지 않다면 오른쪽 형제 노드에서 빌려온다. 만약 형제 노드 모두 최소 조건만을 만족하고 있어 빌릴 수 없는 경우에는 부모 노드의 분리자 키를 내려받고, 현재 노드와 형제 노드를 하나로 병합한다. 이 과정에서 부모 노드의 키가 줄어들게 되며, 부모 노드 역시 최소 조건을 만족하지 못한다면 동일한 재조정 과정이 상위로 전파된다.

현재 상황에서는 삭제된 값 5가 가장 왼쪽 노드에 존재했기 때문에, 왼쪽 형제가 없어 오른쪽 형제 노드의 도움을 받게 된다. 이처럼 B+ Tree의 삭제 과정은 단순히 값을 제거하는 데서 끝나지 않고, 최소 개수 조건을 만족하도록 형제 노드와 부모 노드까지 포함한 연쇄적인 재조정 과정을 거쳐 트리의 균형을 유지한다.

삭제 대상이 내부 노드의 인덱스이고 재조정이 필요하지 않는 경우

위 그림에서 값 45를 삭제하는 경우를 살펴보자. 45가 삭제되더라도 이는 맨 오른쪽 리프 노드에서 발생하므로 해당 노드는 여전히 최소 개수 조건을 만족한다. 따라서 별도의 재조정 과정은 필요하지 않다.

다만 주의할 점은, 45가 내부 노드(Interval Node) 의 인덱스로도 사용되고 있었다는 것이다. 이 경우 삭제된 45 대신 같은 노드 안에 존재하는 다음 Key인 55가 새로운 인덱스로 올라가게 된다. 즉, 리프 노드의 데이터 삭제는 트리 구조 자체를 흔들지는 않지만, 내부 노드의 인덱스 값은 변경될 수 있다.

정리하면, 삭제된 키가 내부 노드의 인덱스였을 경우, 그 인덱스는 해당 리프 노드의 새로운 최소값으로 교체된다. 만약 해당 리프 노드가 완전히 비거나 병합되는 상황이라면, 인접 리프 노드의 최소값이 새로운 인덱스로 사용된다.

삭제 대상이 내부 노드의 인덱스이고 재조정이 필요한 경우

값 25를 삭제하는 상황을 가정해보자. 25를 삭제하면 해당 노드가 최소 개수 조건을 만족하지 않게 되므로 트리의 균형을 맞추기 위한 재조정이 필요하다. 먼저 형제 노드로부터 키를 빌려서 문제를 해결하려 시도하지만, 형제 노드 역시 여유 키가 충분하지 않으므로 병합(merge)을 수행하게 된다.

이때 삭제된 값이 내부 노드의 인덱스였던 경우, 그 자리는 중위 계승자(inorder successor)로 대체되어 내부 노드의 키를 유지한다. 이렇게 연쇄적인 병합과 계승자 대체 과정을 거치면서 B+ Tree의 균형이 유지된다.

번외) InnoDB에서 세컨더리 인덱스가 프라이머리 키를 저장하는 이유

InnoDB 테이블의 모든 세컨더리 인덱스는 레코드의 물리적 주소가 아니라 프라이머리 키 값을 저장하도록 구현되어 있다. 그 이유를 이해하려면 먼저 InnoDB의 구조를 살펴볼 필요가 있다.

InnoDB 테이블은 클러스터드 인덱스(Primary Key 기반 B+Tree) 구조로 저장된다. 각 데이터 레코드는 클러스터드 인덱스에 따라 정렬되고, 데이터 자체가 인덱스 노드에 포함된다. 즉, 프라이머리 키를 기준으로 레코드가 실제 디스크 상의 페이지 단위로 배치된다.

이때 세컨더리 인덱스를 설계할 때 레코드의 물리 주소를 저장한다고 가정해보자. 만약 클러스터드 테이블의 데이터가 이동하면, 즉 레코드가 저장된 물리 페이지가 바뀌거나 페이지 스플릿(split)이 발생하면, 해당 레코드의 주소가 바뀌게 된다. 이렇게 되면 세컨더리 인덱스에 저장된 주소값도 모두 갱신해야 한다. 이는 테이블에 세컨더리 인덱스가 많을수록 매우 큰 오버헤드를 발생시킨다.

실제로 InnoDB에서는 페이지가 가득 찼을 때 B+Tree의 삽입 과정과 유사하게 페이지 분할(Page Split)이 발생한다. 기존 페이지의 절반 정도 레코드가 새 페이지로 이동하게 되면서, 물리 주소가 바뀌고, 만약 세컨더리 인덱스가 주소값을 직접 참조하고 있었다면 모든 관련 인덱스를 갱신해야 한다. 이는 성능상 매우 부담스럽다.

반면, 프라이머리 키 값은 고유하며 변동이 거의 없기 때문에 세컨더리 인덱스가 이를 참조하도록 설계하면 주소값 변경 문제를 피할 수 있다. 세컨더리 인덱스에서 프라이머리 키를 통해 클러스터드 인덱스를 조회하면, 항상 최신 레코드 위치를 찾을 수 있다. 즉, 세컨더리 인덱스가 주소 대신 프라이머리 키를 저장하는 것은 InnoDB의 클러스터드 구조와 페이지 단위 레코드 이동을 고려한 설계상의 선택이다.