B-Tree와 B+Tree란?

[haeyoon1]

B-Tree와 B+Tree 각각에 대해 설명해주세요!

[Uechann]

B-Tree

데이터를 정렬된 상태로 유지하면서, 한 노드에 여러개의 키와 자식에 대한 포인터를 담을 수 있는 다진 균형 트리이다.
이진 트리처럼 자식이 2개로 제한되지 않으며, 한 노드가 2개 이상의 자식을 가질 수 있어서 트리의 높이가 매우 낮게 유지된다.

B+Tree

B-Tree의 변형 버전이다.

차이점 2가지

1. 실제 데이터는 리프 노드에만 저장이 된다. 내부 노드들은 오직 탐색 경로 안내용 키만 가진다.
2. 리프 노드들이 연결 리스트로 서로 이어져 있다.

대부분의 데이터 베이스 (MySQL의 InnoDB, PostgreSQL 등)와 파일 시스템(NTFS, ext4)의 인덱스는 B-Tree가 아니아 B+Tree를 쓴다고 한다.

어떤 문제를 해결하려고 나왔나?

B+Tree는 디스크의 I/O를 최소화하자는 목적으로 나오게 되었다.

메모리(RAM) 접근은 나노초 단위인데, 디스크 접근은 밀리초 단위이다.
약 10만 배 차이가 나게된다. 그래서 데이터가 메모리에 다 안들어가고 디스크에 있어야 하는 상황 (대부분의 DB)에서는, 비교 횟수 보다 디스크 접근 횟수 를 줄이는게 훨씩 중요하였다.

이진 탐색 트리 BST나 AVL, Red-Black Tree는 한 노드에 키가 1개뿐이라 데이터가 많아지면 트리의 높이가 깊어진다.
즉, 디스크를 그만큼 많이 읽어야 한다 즉, 속도가 느리게 된다.

그레서 한번 디스크에서 블록을 읽어올 때 어차피 4KB, 8KB 씩 통째로 읽어오는데,
그 블록 안에 키를 최대한 많이 욱여넣다는 발상이 B-Tree라고 한다.

어떻게 동작하나? (큰 그림)

B-Tree

• 한 노드 = 디스크 블록 1개 (보통 4KB, 8KB, 16KB)
• 한 노드 안에 정렬된 키 여러개 + 자식 포인터들이 들어있음
• 모든 리프 노드는 같은 깊이 (균형 트리)
• 탐색: 루트에서 시작해서 노드 안에서 키를 비교해 어느 자식으로 갈지 결정하면서 리프 노드까지 내려감
• 삽입/삭제 시에 노드가 너무 차거나 빔ㄴ 분할 또는 병합을 하여 균형을 유지한다.

B+Tree

• 내부 노드는 길잡이 역할만 하고, 실제 값은 리프에만 있다.
• 내부 노드에 키를 더 많이 넣을 수 있어서 트리 높이가 더 낮아진다.
• 리프가 연결 리스트로 묶여 있어서 범위 검색 이 매우 빠르다.
  예를 들어서 WHERE age BETWEEN 20 AND 30 은 시작 지점만 트리로 찾고, 그 다음부터는 리프 리스트를 순차적으로 쭉 읽으면 끝이다.

수십억 건의 데이터이어도 트리의 높이가 3-4단계만 거치면 도달할 수 있게 된다고 한다.
즉, 디스크를 3-4번만 읽으면 원하는 데이터를 찾을 수 있다고 한다.

B-TREE와 B+TREE 구조와 범위 검색 시 시각화

B-Tree

flowchart TD
    R["루트[ 10 | 18 ]Bob, Jin"]
    L1["리프 1[ 7 | 8 ]Ann, Carl"]
    L2["리프 2[ 12 | 15 ]Dave, Eve"]
    L3["리프 3[ 22 | 25 ]Frank, Grace"]

    R ---|"< 10"| L1
    R ---|"10 ~ 18"| L2
    R ---|"> 18"| L3

    classDef root fill:#CECBF6,stroke:#534AB7,stroke-width:1px,color:#26215C
    classDef leaf fill:#9FE1CB,stroke:#0F6E56,stroke-width:1px,color:#04342C
    class R root
    class L1,L2,L3 leaf

Loading

B+Tree

flowchart TD
    R["루트 (길잡이만)[ 10 | 18 ]"]
    L1["리프 1[ 7 | 8 ]Ann, Carl"]
    L2["리프 2[ 10 | 12 | 15 ]Bob, Dave, Eve"]
    L3["리프 3[ 18 | 22 | 25 ]Jin, Frank, Grace"]

    R ---|"< 10"| L1
    R ---|"10 ~ 18"| L2
    R ---|">= 18"| L3

    L1 <-.->|"연결 리스트"| L2
    L2 <-.->|"연결 리스트"| L3

    classDef root fill:#CECBF6,stroke:#534AB7,stroke-width:1px,color:#26215C
    classDef leaf fill:#9FE1CB,stroke:#0F6E56,stroke-width:1px,color:#04342C
    class R root
    class L1,L2,L3 leaf

Loading

범위 쿼리 검색 비교

flowchart TB
    subgraph BT["B-Tree (위아래 왕복: 4회 읽기)"]
        direction TB
        BR["루트[ 10 | 18 ]"]
        BL1["리프[ 12 | 15 ]"]
        BL2["리프[ 22 | 25 ]"]
        BR ==>|"1"| BL1
        BL1 -.->|"2. 다시 루트로"| BR
        BR ==>|"3"| BL2
    end

    subgraph BP["B+Tree (옆으로 이동: 3회 읽기)"]
        direction TB
        PR["루트[ 10 | 18 ]"]
        PL1["리프[ 10 | 12 | 15 ]"]
        PL2["리프[ 18 | 22 | 25 ]"]
        PR ==>|"1"| PL1
        PL1 ==>|"2. 연결 리스트로"| PL2
    end

    classDef root fill:#CECBF6,stroke:#534AB7,stroke-width:1px,color:#26215C
    classDef leaf fill:#9FE1CB,stroke:#0F6E56,stroke-width:1px,color:#04342C
    class BR,PR root
    class BL1,BL2,PL1,PL2 leaf

Loading

[sangjun121]

결론 정리

우선 B+Tree는 B-Tree를 변형한 개념이며, MySQL의 InnoDB 스토리지 엔진은 인덱스 저장에 B+Tree를 사용하여 디스크IO작업의 성능을 높입니다.

B-트리와 B+트리란 무엇인가?

B-트리는 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드가 2개 이상 가능한 트리구조를 의미합니다. 여기에 각 노드에는 key-value쌍이 들어가게 되는데, 리프 노드를 제외한 노드는 키값만 갖고 있고, 리프 노드만 value를(실제 value가 아닌 디스크의 메모리 주소) 갖는 변형된 트리구조를 B+트리라고 합니다.

B-트리가 데이터베이스에서 중요한 이유

B-트리는 균형 잡힌 다진 탐색 트리입니다.(즉, 한 노드에 여러 key를 저장하고 여러 자식을 가질 수 있다는 의미) 데이터베이스는 데이터를 페이지 단위로 읽기 때문에, B-트리 계열은 한 노드가 하나의 페이지에 대응되도록 설계할 수 있고 한 번의 페이지 읽기로 많은 key를 비교할 수 있습니다. 그래서 트리의 높이가 낮아지고(탐색 시간이 log(n)이므로 낮을 수록 탐색 성능이 좋아집니다.) 원하는 데이터를 찾기 위해 접근해야 하는 페이지 수가 줄어듭니다. 즉, 디스크 IO작업이 줄어들기 때문에 효율적입니다.

B+트리를 사용하여 노드 내부 키 개수 증가로, 디스크 작업 더 최적화

B-트리는 내부 노드와 리프 노드 모두에 실제 데이터나 데이터 포인터가 저장될 수 있습니다. 반면 B+트리는 내부 노드에는 탐색용 key만 두고 실제 데이터가 저장된 주소(value)는 리프 노드에만 두고, 리프 노드끼리는 순서대로 연결리스트로 연결되어 있습니다. 이 차이 때문에 B+Tree는 범위 검색에 강합니다. 예를 들어 BETWEEN 20 AND 30 같은 조건에서는 시작 key를 찾은 뒤 리프 노드를 연결리스트로 순서대로 따라가며 원하는 데이터를 찾을 수 있습니다.

내부 노드에는 탐색 key만 있으므로 더 많은 key를 담을 수 있기에 트리 높이도 낮게 유지시켜 탐색 성능을 향상시킬 수 있습니다. 그래서 DB 인덱스에서는 실제 구현은 B+Tree인 경우가 많습니다. MySQL InnoDB의 인덱스도 B+Tree 기반으로 구현되어 있습니다.