B+ 트리

B+ 트리의 각 노드는 여러 개의 키와 포인터를 저장하는 레코드로 구성된다. 내부 노드(인덱스 노드)는 키 값과 자식 노드를 가리키는 포인터만을 가지며, 실제 데이터는 오직 리프 노드에만 저장된다. 이는 B 트리와 구분되는 핵심적인 특징이다.

리프 노드는 키 값과 그에 해당하는 실제 데이터 레코드의 위치(예: 데이터베이스의 ROWID)를 저장하는 데이터 포인터를 포함한다. 또한, 모든 리프 노드는 양방향 연결 리스트로 서로 연결되어 있어, 특정 범위의 데이터에 대한 순차적 접근(범위 질의)을 매우 효율적으로 수행할 수 있게 해준다.

각 노드가 가질 수 있는 키와 포인터의 최대 개수는 트리의 차수에 의해 결정된다. 노드는 일반적으로 디스크의 페이지나 블록 크기에 맞춰 설계되어, 한 번의 디스크 입출력으로 전체 노드를 읽거나 쓸 수 있도록 함으로써 입출력 효율성을 극대화한다.

B+ 트리의 가장 큰 특징 중 하나는 모든 리프 노드가 연결 리스트 형태로 서로 연결되어 있다는 점이다. 이는 B+ 트리가 B-트리와 구분되는 핵심적인 차이점이다. B-트리에서는 모든 노드가 키와 실제 데이터를 함께 저장하는 반면, B+ 트리에서는 실제 데이터는 오직 리프 노드에만 저장되고, 내부 노드(인덱스 노드)는 검색을 위한 키만을 가진다.

이렇게 모든 리프 노드가 연결되면, 특정 범위 내의 데이터를 순차적으로 접근하는 범위 질의가 매우 효율적으로 이루어진다. 예를 들어, 'A'부터 'K'까지의 모든 레코드를 찾고자 할 때, B-트리는 각 키를 찾기 위해 루트 노드부터 반복적으로 탐색해야 할 수 있다. 반면, B+ 트리는 먼저 'A'가 위치한 리프 노드를 찾은 후, 리프 노드 간의 연결 포인터를 따라 순차적으로 다음 노드로 이동하며 'K'까지의 모든 데이터를 빠르게 읽을 수 있다. 이는 데이터베이스에서 자주 수행되는 범위 검색이나 전체 테이블 스캔 성능을 크게 향상시킨다.

또한, 이 연결 구조는 파일 시스템에서도 유용하게 작용한다. 대용량 파일을 순차적으로 읽거나, 디렉토리 내의 모든 파일 목록을 나열할 때, 리프 노드의 연결을 통해 디스크 상에 연속적으로 저장되지 않은 데이터 블록들도 논리적으로 순차 접근이 가능해진다. 이는 물리적인 디스크 I/O 횟수를 줄여 전체 시스템 성능을 높이는 데 기여한다.

결론적으로, 리프 노드의 연결은 B+ 트리가 단순한 랜덤 액세스뿐만 아니라 효율적인 순차 액세스도 지원하도록 만들어, 인덱싱이 필요한 다양한 저장소 시스템에서 선호되는 자료구조가 되게 한 핵심 설계 요소이다.

B+ 트리는 모든 리프 노드가 같은 깊이를 유지하는 균형 트리이다. 이 균형 성질은 트리의 높이가 데이터 항목 수에 대해 로그 함수적 증가를 보장하여, 검색, 삽입, 삭제 연산의 효율성을 유지하는 핵심이다. 균형은 주로 삽입과 삭제 연산 과정에서 노드가 정의된 최소 및 최대 키 개수 범위를 벗어나지 않도록 조정함으로써 유지된다.

삽입 연산 시, 대상 리프 노드에 여유 공간이 있으면 단순히 키를 삽입한다. 그러나 노드가 가득 차면 노드 분할이 발생한다. 분할은 가득 찬 노드의 키들을 두 개의 노드로 나누고, 중간 키를 부모 노드로 올려서 부모 노드의 인덱스 항목을 갱신하는 과정이다. 이 과정이 재귀적으로 부모 노드로 전파될 수 있으며, 결과적으로 트리의 높이가 증가할 수 있다.

삭제 연산 시, 키를 리프 노드에서 제거한 후 노드의 키 개수가 최소 요구치 미만으로 떨어지면 트리 균형이 깨진다. 이를 해결하기 위해 형제 노드로부터 키를 빌려오는 재분배나, 형제 노드와의 병합 연산이 수행된다. 병합은 키 개수가 부족한 노드를 인접한 형제 노드와 합치고, 부모 노드의 해당 인덱스 항목을 제거하는 것이다. 삭제로 인한 병합 역시 부모 노드로 재귀적으로 전파되어, 최악의 경우 트리의 높이가 줄어들 수 있다.

이러한 분할과 병합 메커니즘을 통해 B+ 트리는 동적인 데이터 갱신이 빈번히 일어나는 환경에서도 구조적 균형을 지속적으로 유지한다. 이는 데이터베이스 관리 시스템의 인덱스나 파일 시스템의 메타데이터 관리와 같은 응용 분야에서 안정적인 성능을 제공하는 기반이 된다.

B+ 트리에서 검색 연산은 루트 노드에서 시작하여 리프 노드에 도달할 때까지 트리를 순회하는 방식으로 이루어진다. 각 내부 노드는 여러 개의 키와 자식 노드에 대한 포인터를 가지며, 이 키들은 정렬된 상태를 유지한다. 검색 알고리즘은 찾고자 하는 키 값과 노드 내의 키들을 비교하여, 해당 키가 속할 수 있는 범위를 가리키는 포인터를 따라 다음 자식 노드로 내려간다.

이 과정은 리프 노드에 도달할 때까지 반복된다. B+ 트리의 모든 실제 데이터 레코드에 대한 포인터 또는 키 값 자체는 오직 리프 노드에만 저장되기 때문에, 검색은 반드시 리프 노드에서 완료된다. 리프 노드에 도달하면, 노드 내에서 선형 탐색 또는 이진 탐색을 통해 목표 키를 찾는다. 검색의 시간 복잡도는 트리의 높이에 비례하며, 이는 대수 함수적(log 시간)으로 매우 효율적이다.

이러한 검색 방식은 데이터베이스의 인덱스나 파일 시스템에서 대량의 데이터 블록을 효율적으로 접근하는 데 적합하다. 또한 모든 리프 노드가 연결 리스트 형태로 연결되어 있어, 특정 범위의 키를 검색하는 범위 질의나 전체 데이터를 순차적으로 접근하는 데도 유리하다[1].

삽입 연산은 새로운 키를 B+ 트리에 추가하는 과정이다. 삽입은 항상 리프 노드에서 시작되며, 트리의 균형을 유지하기 위해 노드 분할이 발생할 수 있다.

삽입 과정은 먼저 키가 속해야 할 리프 노드를 검색을 통해 찾는 것으로 시작한다. 해당 리프 노드에 여유 공간이 있다면, 키는 정렬된 순서를 유지하며 노드 내 적절한 위치에 삽입된다. 그러나 노드가 이미 최대 키 개수로 가득 찼다면 오버플로가 발생하여 노드 분할이 필요해진다. 분할 시 중간 키를 기준으로 노드가 두 개로 나뉘며, 중간 키는 부모 노드로 승격되어 인덱스 역할을 하게 된다. 이 승격 과정이 부모 노드에서도 오버플로를 일으킬 경우, 분할과 승격이 루트 노드에 이를 때까지 재귀적으로 반복된다. 루트 노드가 분할되면 트리의 높이가 증가한다.

이러한 삽입 알고리즘은 모든 리프 노드가 동일한 깊이를 유지하도록 보장하며, 이는 효율적인 순차 접근의 기반이 된다. 또한 인덱스 노드에는 실제 데이터에 대한 포인터가 아닌 키 값과 자식 노드를 가리키는 포인터만 저장되므로, 노드 분할이 발생하더라도 데이터 레코드 자체의 물리적 위치는 영향을 받지 않는다는 장점이 있다. 이는 데이터베이스 관리 시스템과 파일 시스템에서 안정적인 성능을 제공하는 데 기여한다.

B+ 트리의 삭제 연산은 특정 키를 트리에서 제거하는 과정이다. 삭제는 항상 리프 노드에서 시작되며, 이는 B+ 트리의 핵심 특성이다. 키가 내부 노드에 존재하더라도 실제 데이터 항목은 리프 노드에만 저장되므로, 최종 삭제 대상은 항상 리프 노드가 된다. 삭제 후에도 트리의 균형과 노드의 최소 키 개수 조건을 유지해야 한다.

삭제 과정은 먼저 검색 연산을 통해 해당 키가 위치한 리프 노드를 찾는 것으로 시작한다. 키를 리프 노드에서 제거한 후, 해당 노드의 키 개수가 최소 요구치 미만으로 떨어지지 않으면 연산이 종료된다. 그러나 키 개수가 최소치보다 적어지면, 트리는 균형을 복구하기 위한 작업을 수행한다. 주로 인접한 형제 노드로부터 키를 빌려오는 재분배를 시도하거나, 형제 노드와의 병합을 통해 노드를 하나로 합치는 방법을 사용한다.

병합이 발생하면 부모 노드의 키도 함께 제거되어야 하므로, 삭제의 영향이 상위 노드로 전파될 수 있다. 이 과정은 루트 노드에 도달하거나, 노드의 키 개수가 최소 조건을 만족할 때까지 재귀적으로 반복된다. 결과적으로 루트 노드의 키가 모두 사라져 자식이 하나만 남는 경우, 해당 자식 노드를 새로운 루트로 만들고 기존 루트를 제거함으로써 트리의 높이가 줄어들기도 한다. 이러한 삭제 알고리즘은 모든 리프 노드가 동일한 깊이를 유지하도록 보장하며, 순차 접근의 효율성을 유지하는 데 결정적이다.

B+ 트리는 데이터베이스 관리 시스템에서 인덱스를 구현하는 데 가장 널리 사용되는 자료구조이다. 관계형 데이터베이스를 포함한 많은 현대 데이터베이스는 테이블의 기본 키나 다른 칼럼에 대한 인덱스를 생성할 때 내부적으로 B+ 트리를 채택한다. 이는 B+ 트리가 대용량 데이터에 대해 안정적인 로그 시간의 검색 성능을 보장하면서도, 범위 질의와 같은 순차 접근에 매우 효율적이기 때문이다.

데이터베이스 인덱스로서 B+ 트리의 핵심 장점은 모든 실제 데이터 레코드에 대한 포인터가 오직 리프 노드에만 저장된다는 점이다. 이로 인해 내부 노드는 단순히 키 값과 자식 노드를 가리키는 포인터만을 저장하여 하나의 노드에 더 많은 키를 담을 수 있게 된다. 결과적으로 트리의 높이가 낮아져 디스크 접근 횟수를 최소화할 수 있으며, 이는 하드 디스크 드라이브와 같은 보조기억장치 기반 시스템에서 매우 중요한 성능 요소이다.

또한, 모든 리프 노드가 연결 리스트 형태로 서로 연결되어 있어 특정 키 값에서 시작해 그 이후 또는 이전의 모든 레코드를 순차적으로 접근하는 범위 질의의 처리 효율이 극대화된다. 예를 들어, "A부터 D까지의 고객을 찾아라"라는 질의는 먼저 키 'A'를 검색한 후, 리프 노드들의 연결을 따라 순차 스캔만으로 결과를 빠르게 모을 수 있다. 이러한 특성은 온라인 트랜잭션 처리 시스템에서 빈번하게 발생하는 정렬 및 부분 범위 검색에 적합하다.

대표적인 오픈 소스 데이터베이스인 MySQL의 InnoDB 스토리지 엔진이나 PostgreSQL 등은 테이블의 클러스터형 인덱스와 보조 인덱스를 모두 B+ 트리 구조로 관리한다. 이는 데이터 무결성을 유지하면서 대량의 삽입, 삭제, 갱신 연산이 발생하는 환경에서도 비교적 균형 잡힌 트리 구조를 유지하도록 설계되었기 때문이다.

파일 시스템은 컴퓨터에서 데이터를 저장하고 구성하는 방법을 정의하는 운영체제의 핵심 구성 요소이다. B+ 트리는 이러한 파일 시스템에서 디렉터리 구조 관리와 파일 할당 테이블의 대안으로 사용되어, 대용량 저장 장치에서 파일의 메타데이터와 실제 데이터 블록의 위치를 효율적으로 색인하고 관리하는 데 기여한다. 특히 저널링 파일 시스템이나 확장 파일 시스템과 같은 현대적인 파일 시스템에서 그 활용이 두드러진다.

파일 시스템에서 B+ 트리의 주요 장점은 빠른 파일 탐색과 효율적인 순차 접근을 동시에 제공한다는 점이다. 리프 노드가 연결 리스트로 연결되어 있어, 특정 파일을 찾는 검색뿐만 아니라 디렉터리 내의 모든 파일을 순차적으로 읽어야 하는 작업에도 유리하다. 이는 파일 시스템이 디렉터리 엔트리를 관리하거나, 매우 큰 파일의 익스텐트 정보를 저장할 때 안정적인 성능을 보장한다.

대표적인 예로, ReiserFS 파일 시스템은 메타데이터와 작은 파일의 데이터 자체를 B+ 트리에 직접 저장하는 방식으로 설계되었다. 또한 NTFS와 XFS와 같은 고성능 파일 시스템들도 마스터 파일 테이블이나 inode의 확장 속성 관리와 같은 내부 구조에 B+ 트리 또는 그 변형 알고리즘을 채택하여 대용량 볼륨에서의 성능과 확장성을 높였다.