[DB] B-tree와 B+tree

B-tree(Balanced Tree)란?

정의

• B-tree(균형 다진법 트리)는 대용량 데이터를 빠르게 검색, 삽입, 삭제할 수 있도록 설계된 자료구조

주요 특징

균형성

• 모든 리프 노드가 동일한 깊이에 위치해 최악의 경우에도 O(log n)의 시간 복잡도를 유지

다진 트리 구조

• 한 노드가 여러 개의 자식 노드를 가질 수 있어, 한 번의 디스크 I/O로 많은 데이터를 읽어들일 수 있음

키와 포인터

• 각 내부 노드는 여러 개의 키와 자식 노드에 대한 포인터를 저장하며, 리프 노드는 실제 데이터(또는 데이터 레코드의 포인터)를 저장

Fan-out

• 한 노드에 저장할 수 있는 키의 수(또는 차수)가 높을수록 트리의 높이가 낮아지고, 결과적으로 디스크 접근 횟수가 줄어듬

---

B+ tree란?

정의

• B+ tree는 B-tree의 변형으로, 모든 실제 데이터를 리프 노드에만 저장하고 내부 노드는 오직 탐색용 키 값만 유지

 

특징

범위 검색 최적화

• 리프 노드들이 연결 리스트(Linked List) 형태로 연결되어 있어, 연속된 범위의 데이터를 빠르게 읽을 수 있음

높은 데이터 밀도

• 내부 노드에 저장되는 정보가 적어 한 페이지에 더 많은 키를 저장할 수 있으므로 디스크 공간 활용이 우수

실제 DBMS 활용

• MySQL InnoDB, PostgreSQL 등의 데이터베이스 시스템에서는 주로 B+ tree 인덱스를 사용

---

삽입 및 삭제 알고리즘과 노드 분할/병합

삽입(Insertion)

B-tree 삽입 과정

1. 탐색: 루트부터 시작해 삽입할 위치(리프 노드)를 찾음
2. 삽입: 리프 노드에 빈 공간이 있다면 키를 직접 삽입
3. 노드 분할: 만약 리프 노드가 이미 가득 찼다면, 노드를 중간값을 기준으로 두 개로 분할하고, 그 중간값을 부모 노드로 올림
4. 재귀적 처리: 부모 노드도 공간이 부족할 경우, 동일한 분할 과정을 재귀적으로 수행

---

B+ tree 삽입 과정

1. 탐색: 리프 노드를 찾아 삽입할 위치를 결정
2. 삽입 및 분할: 리프 노드에 공간이 없으면 노드를 분할하고, 분할된 두 노드를 연결 리스트 형태로 유지
3. 내부 노드 업데이트: 분할 시 발생한 중간 키를 상위 내부 노드에 삽입하며, 필요하면 내부 노드 역시 분할

---

삭제(Deletion)

B-tree 삭제 과정

1. 탐색: 삭제할 키를 포함하는 노드를 찾음
2. 삭제: 리프 노드에서 직접 삭제하거나, 내부 노드의 경우 대체 키(예: 중위 순회 전후의 값)로 대체 후 삭제
3. 균형 유지: 삭제 후 해당 노드의 키 개수가 최소 기준보다 낮아지면, 인접 형제 노드와 키를 재분배하거나 두 노드를 병합(merge)하여 트리 균형을 복원

---

B+ tree 삭제 과정

1. 탐색 및 삭제: 리프 노드에서 삭제할 키를 제거
2. 재분배 및 병합: 삭제 후 해당 노드의 키 개수가 최소 기준보다 적으면, 형제 노드와 키를 재분배하거나 병합하여 균형을 맞춤
3. 내부 노드 업데이트: 내부 노드에는 리프 노드의 최소 키만 관리되므로, 삭제 시 내부 노드의 수정은 상대적으로 단순

---

의사코드 예제 (B+ tree 삽입)

function insert(BPlusTree tree, Key key, Data value):
    leaf = findLeafNode(tree.root, key)
    if leaf.hasSpace():
        leaf.insert(key, value)
    else:
        newLeaf = leaf.split()       // 노드 분할: 현재 리프 노드를 두 개로 분할
        if key > newLeaf.firstKey():
            newLeaf.insert(key, value)
        else:
            leaf.insert(key, value)
        // 부모 노드 업데이트: 분할된 두 노드의 정보를 부모에 반영
        insertInParent(tree, leaf, newLeaf.firstKey(), newLeaf)

function insertInParent(tree, Node left, Key key, Node right):
    if left is tree.root:
        newRoot = createNode()
        newRoot.keys = [key]
        newRoot.children = [left, right]
        tree.root = newRoot
    else:
        parent = left.parent
        if parent.hasSpace():
            parent.insert(key, right)
        else:
            newParent = parent.split()
            insertInParent(tree, parent, newParent.firstKey(), newParent)

---

성능 분석 및 디스크 I/O 효율성

시간 복잡도(검색, 삽입, 삭제)

• B-tree와 B+ tree는 모두 O(log n)의 시간 복잡도를 보장
• 균형 잡힌 구조 덕분에 데이터의 양이 많아져도 성능 저하가 일정하게 유지

---

공간 활용

B-tree

• 내부와 리프 노드 모두 데이터를 저장하므로 한 페이지에 저장할 수 있는 키의 수가 제한될 수 있음

B+ tree

• 내부 노드에 탐색용 키만 저장하여 한 페이지에 더 많은 키를 저장할 수 있고, 이는 디스크 공간 활용 측면에서 효율적

---

디스크 I/O 최적화

높은 Fan-out

• 한 노드에 많은 자식 포인터를 저장할 수 있어 트리의 높이가 낮아지고, 결과적으로 디스크 접근 횟수가 줄어듬

연결된 리프 노드 (B+ tree)

• 범위 검색 시 인접 리프 노드들을 순차적으로 읽어들이므로, 캐시 효율과 디스크 I/O 성능이 향상

---

면접 대비 질문

기본 질문

Q1. B-tree란 무엇인가요?

모범 답안:
B-tree(균형 다진법 트리)는 대용량 데이터를 빠르게 검색, 삽입, 삭제하기 위해 설계된 균형 잡힌 다진 트리 구조입니다. 모든 리프 노드가 동일한 깊이에 위치하며, 한 노드에 여러 개의 자식 노드를 둘 수 있어 디스크 I/O를 최소화하고, O(log n) 시간 복잡도를 보장합니다.

---

Q2. B+ tree란 무엇이며, B-tree와의 차이점은 무엇인가요?

모범 답안:
B+ tree는 B-tree의 변형으로, 모든 실제 데이터(또는 레코드 포인터)를 리프 노드에 저장하고, 내부 노드는 탐색용 키 값만 유지합니다. 이로 인해 범위 검색이 매우 효율적이며, 한 페이지에 더 많은 키를 저장할 수 있어 디스크 공간 활용이 뛰어납니다. 반면, 일반 B-tree는 내부 노드에도 데이터를 저장합니다.

---

Q3. B-tree와 B+ tree가 데이터베이스에서 인덱스로 사용되는 이유는 무엇인가요?

모범 답안:
두 트리 모두 균형 잡힌 구조를 가지므로 데이터 검색, 삽입, 삭제 시 O(log n)의 시간 복잡도를 유지합니다. B+ tree는 특히 범위 검색과 정렬에 유리하며, 높은 Fan-out을 통해 디스크 I/O를 최소화하므로 대용량 데이터베이스 인덱스로 적합합니다.

---

심화 질문

Q4. B-tree 삽입 시 노드 분할(Split)은 어떻게 이루어지나요?

모범 답안:
삽입할 위치의 리프 노드에 공간이 없으면 해당 노드를 중간값 기준으로 두 개로 분할합니다. 분할된 후, 중간값은 부모 노드로 올려지게 되며, 만약 부모 노드 역시 공간이 부족하면 같은 분할 과정을 재귀적으로 적용하여 트리 전체의 균형을 유지합니다.

---

Q5. B+ tree에서 삭제 시 노드 병합(Merge)과 재분배(redistribution)의 과정은 어떻게 진행되나요?

모범 답안:
B+ tree에서 삭제 후 리프 노드의 키 개수가 최소 기준보다 적어지면, 인접한 형제 노드와 키를 재분배하여 균형을 맞춥니다. 만약 재분배가 불가능한 경우, 두 노드를 병합하여 하나의 노드로 결합하고, 이 변경 사항을 상위 노드에 반영하여 트리의 균형을 복원합니다.

---

Q6. 높은 Fan-out이 B-tree/B+ tree의 성능에 미치는 영향은 무엇인가요?

모범 답안:
높은 Fan-out은 한 노드에 저장할 수 있는 자식의 수를 늘려 트리의 높이를 낮춥니다. 트리 높이가 낮아지면 검색, 삽입, 삭제 시 필요한 디스크 접근 횟수가 줄어들어 전체 성능이 향상됩니다.

---

압박 질문

Q7. B+ tree의 삽입 및 삭제 과정에서 발생하는 다단계 재귀적 업데이트가 성능에 미치는 영향을 설명하고, 이를 해결하기 위한 방안은 무엇인가요?

모범 답안:
재귀적 업데이트는 노드 분할이나 병합 시 여러 단계에 걸쳐 발생하여 다수의 디스크 I/O와 CPU 연산을 요구할 수 있습니다. 이러한 문제는 높은 Fan-out, 효율적인 버퍼 캐시 및 디스크 스케줄링 최적화, 그리고 데이터 삽입의 순차성 보장을 통해 완화할 수 있습니다. 최신 DBMS는 내부적으로 이러한 최적화 기법을 적용하여 성능 저하를 최소화합니다.

---

Q8. 빈번한 노드 분할이 발생할 경우 시스템 성능에 어떤 문제가 생기며, 이를 방지하기 위한 전략은 무엇인가요?

모범 답안:
노드 분할이 빈번하게 발생하면 디스크 I/O가 과도하게 증가하고, 트리 재구성으로 인해 CPU 부하가 상승하여 전체 성능이 저하될 수 있습니다. 이를 방지하기 위해 적절한 노드 크기와 페이지 크기를 설정하고, 데이터 삽입 시 순차적 패턴을 유지하며, 캐시 메커니즘을 활용해 재분배와 병합 과정을 최적화하는 전략을 사용할 수 있습니다.

---

Q9. 만약 B-tree 또는 B+ tree의 균형이 깨진다면, 어떤 문제가 발생하며, 이를 감지하고 해결하기 위한 방법은 무엇인가요?

모범 답안:
트리의 균형이 깨지면 검색, 삽입, 삭제 작업의 시간 복잡도가 O(log n)에서 O(n)으로 상승하여 성능 저하를 초래합니다. 이를 감지하기 위해 주기적으로 트리의 높이와 키 분포를 모니터링하고, 실행 계획(EXPLAIN)을 분석하는 방법을 사용할 수 있습니다. 균형이 깨진 경우, 트리 재구성(rebalancing)이나 인덱스 재구축 등의 방법을 통해 문제를 해결합니다.

---

Reference

https://medium.com/@for.wlb.biz/introduction-to-binary-tree-b-tree-b-tree-1ffd62279963

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Plus-Tree

https://iq.opengenus.org/b-tree-deletion/#google_vignette