로그인회원가입
[C++][포트폴리오] B+ 트리

2026.04.26. 16:24

B+ Tree 자료구조 구현 프로젝트

C++로 직접 구현한 제네릭 B+ Tree 라이브러리

프로젝트 개요

항목 내용 저장소 github.com/metanoia95/BPlusTree 언어 C++ (100%) 빌드 환경 Visual Studio (.slnx, .vcxproj) 핵심 파일 BPlusTree.h, main.cpp, test.h, Timer.h

외부 라이브러리 없이 C++ 표준 라이브러리(<iostream>, <queue>, <vector>, <cassert>)만 사용하여 B+ Tree를 처음부터 직접 구현한 프로젝트입니다. 데이터베이스 인덱스 구조로 널리 활용되는 B+ Tree의 핵심 알고리즘을 완전히 이해하고 손수 구현하는 것을 목표로 했습니다.

기술 스택

  • 언어: C++

  • 패러다임: 템플릿 기반 제네릭 프로그래밍

  • 자료구조: B+ Tree (내부 노드 + 이중 연결 리스트 리프 노드)

  • 빌드 도구: Visual Studio (MSBuild)

구현 내용

핵심 자료구조 설계

템플릿을 활용하여 키(K)와 값(V) 타입을 자유롭게 지정할 수 있는 제네릭 B+ Tree를 설계했습니다.

template<typename K, typename V>
class BPlusTree { ... };

노드(Node) 구조체는 다음 필드를 포함합니다.

  • isLeaf — 리프 노드 여부

  • degree — 트리 차수 (최대 자식 수)

  • keys[] / values[] — 동적 배열로 관리되는 키·값

  • children[] — 자식 노드 포인터 배열 (이중 포인터)

  • parent, prev, next — 부모 및 리프 간 연결 포인터

리프 노드를 이중 연결 리스트로 연결하여 범위 탐색 성능을 O(log N + K)로 유지합니다.

공개 API (Public Interface)

메서드 설명 insert(key, value) 키-값 삽입 및 노드 분할(Split) 처리 search(key) 단건 조회 (이진 탐색 기반) rangeSearch(start, end) 범위 탐색 (리프 연결 리스트 순회) update(key, newValue) 값 수정 erase(key) 키 삭제 및 언더플로우 처리 print() BFS를 이용한 레벨별 트리 출력 printLeaf() 리프 노드 오름차순 순회 출력 printLeafReverse() 리프 노드 내림차순 역방향 순회 출력 clear() 전체 트리 메모리 해제

주요 알고리즘 구현

1. 삽입 & 노드 분할 (Split)

  • 리프 노드 삽입 후 size == degree 조건으로 오버플로우 감지

  • 리프/내부 노드를 구분하여 각각 splitLeafNode() / splitInternalNode() 실행

  • 분할 키를 부모로 올리고 루트 분할 시 새 루트를 자동 생성

2. 삭제 & 언더플로우 처리 (Underflow)

  • 삭제 후 노드가 최소 차수 미만이면 언더플로우 처리

  • 형제 노드에서 빌릴 수 있는 경우 재분배(Redistribute)

  • 빌릴 수 없는 경우 병합(Merge) 수행 후 부모로 재귀 전파

3. 이진 탐색

  • lowerBound(): key ≥ 조건을 만족하는 첫 인덱스 탐색 (리프 노드 조회/삽입 위치)

  • upperBound(): key > 조건을 만족하는 첫 인덱스 탐색 (내부 노드 경로 탐색)

4. 경계키 관리

  • 삭제 후 내부 노드의 경계키가 변경되는 경우 updateParentBoundaryKey()로 갱신

성능 측정

Timer.h와 test.h를 통해 다양한 케이스의 삽입·삭제 성능을 밀리초 단위로 측정합니다.

Timer t;
testOrderAsc(100, tree);    // 오름차순 삽입/삭제
testOrderDesc(30, tree);    // 내림차순 삽입/삭제
testRandom(500, tree);      // 랜덤 삽입/삭제
std::cout << "총 소요시간: " << t.elapsed_ms() << "ms" << std::endl;

기술적 도전과 해결

1. size_t 언더플로우 버그

역방향 순회 시 size_t(unsigned) 타입 변수에서 0 - 1이 최댓값으로 래핑되어 무한 루프가 발생하는 문제를 코드 내 주석으로 명시적으로 기록하고, int 타입으로 교체하여 해결했습니다.

2. 내부 노드 병합 시 자식 포인터 재연결

병합 과정에서 이동된 자식 노드의 parent 포인터가 갱신되지 않으면 트리 무결성이 깨지는 문제가 발생합니다. 재분배/병합 함수 내에서 자식의 parent 포인터를 명시적으로 갱신(outChild->parent = cursor)하여 해결했습니다.

3. 메모리 관리

동적 할당된 keys[], values[], children[] 배열을 소멸자에서 delete[]로 명시적으로 해제하고, clearNode()를 재귀 호출하여 전체 트리의 메모리 누수를 방지했습니다.

배운 점

  • B+ Tree의 삽입·삭제·분할·병합·재분배 알고리즘을 직접 구현하며 내부 동작 원리를 깊이 이해

  • C++ 템플릿을 활용한 제네릭 자료구조 설계 경험

  • size_t vs int 등 타입 선택이 런타임 버그에 미치는 영향을 실제로 경험하고 해결

  • 복잡한 포인터 연결(이중 연결 리스트, 부모-자식 포인터)을 안정적으로 관리하는 방법 체득

GitHub: https://github.com/metanoia95/BPlusTree

목록