B-Tree와 B+ Tree의 차이에 대해 설명해주세요.
면접 답변
B-Tree는 모든 노드에 데이터를 저장하고, 균형을 유지하면서 삽입과 삭제가 가능합니다. 반면에, B+ Tree의 경우 데이터는 리프 노드에만 저장하고, 내부 노드는 탐색용 키만 가집니다. B+ Tree는 모든 데이터를 리프 노드에 정렬된 상태로 저장하고 연결하기 때문에, 순차 접근이나 범위 검색에 훨씬 유리해서 데이터베이스의 인덱스 구조에 적합합니다.
개념 정리
용어 정리
내부 노드와 리프 노드
내부 노드 (Internal Node)
자식 노드를 가지는 노드. 루트 노드를 포함하며 탐색 경로 상에 존재하는 중간 노드를 의미한다. 주로 키만 저장하거나, B-Tree의 경우 키와 데이터를 함께 저장하기도 한다.
리프 노드 (Leaf Node)
자식이 없는 노드, 즉 트리의 가장 마지막 단계에 위치한 노드. 실제 데이터를 저장하는 위치로, B+ Tree에서는 모든 데이터가 리프 노드에만 저장된다.
공통점
다진 탐색 트리(M-way Search Tree)의 일종이다.
균형 잡힌 트리로 삽입/삭제 후에도 트리의 높이를 최소로 유지할 수 있다.
디스크 I/O 최소화를 위해 고안되었다. (블록 단위 접근)
DB 인덱스, 파일 시스템 등에서 사용한다.
cf) 균형 잡힌 트리
B-Tree vs B+ Tree
데이터 저장 위치
내부 노드와 리프 노드 모두에 저장
리프 노드에만 저장
내부 노드 구조
키와 실제 데이터
키만 저장 (실제 데이터는 없음)
리프 노드 구조
키와 데이터가 혼합
전체 데이터가 정렬된 상태로 저장됨 + 다음 리프 노드를 가리키는 포인터 존재
범위 탐색 성능
비효율적 (여러 노드 탐색 필요)
효율적 (리프 노드 간 연결로 순차 탐색 가능)
트리 높이
상대적으로 낮을 수 있음
더 많은 키를 내부 노드에 저장하므로 높이가 낮음 (검색 속도 빠름)
사용 예시
파일 시스템, 일부 간단한 인덱스 구조
대부분의 관계형 데이터베이스 인덱스 (MySQL, PostgreSQL, Oracle 등)
구조 예시
B-Tree 구조
[20]: 내부 노드 (루트 노드이자 탐색 키를 가지고 있고, 데이터도 가질 수 있다.)
[10], [25, 30]: 리프 노드 (실제 데이터 포함 가능)
B+ Tree 구조
[20]: 내부 노드 (탐색 키만 존재하고, 데이터는 존재하지 않는다.)
[10], [25, 30]: 리프 노드 (모든 데이터를 저장하고 있고, 포인터로 서로 연결되어 있다.)
꼬리 질문
왜 대부분의 데이터베이스는 B+ Tree를 인덱스로 사용할까요? B+ Tree는 균형 잡힌 트리 구조로, 높이를 낮게 유지하면서 검색, 삽입, 삭제 시 디스크 접근 횟수를 최소화할 수 있기 때문입니다. 또한 모든 데이터를 리프 노드에만 저장하고 리프 노드끼리 연결되어 있어, 범위 검색을 빠르고 효율적으로 수행할 수 있습니다.
B+ Tree의 리프 노드가 포인터로 연결되어 있는 이유는 무엇인가요? B+ Tree의 리프 노드는 왼쪽에서 오른쪽으로 순차 연결된 포인터(링크드 리스트 구조)를 가지고 있는데, 이 연결 구조는 범위 검색을 빠르게 처리하기 위함입니다. 예를 들어, WHERE id BETWEEN 100 AND 200 같은 쿼리를 실행할 때 시작 위치만 찾은 뒤 연결된 노드를 따라가면서 빠르게 연속된 데이터를 탐색할 수 있습니다.
B+ Tree의 단점은 없나요? 모든 데이터를 리프 노드에만 저장하므로, 데이터가 많은 경우 리프 노드가 커지고 디스크 공간을 더 많이 사용할 수 있습니다. 그리고 삽입/삭제 시 노드 분할과 병합이 발생하면 재구성 비용이 발생할 수 있으며, 특히 대규모 업데이트 작업에서는 성능 저하가 있을 수 있습니다.
Last updated