B-Tree와 데이터베이스 인덱스 완전 분석

개요

B-Tree는 디스크 기반 시스템을 위해 설계된 자가 균형 다진 트리입니다. 각 노드가 여러 키와 자식을 보유하며, 한 번의 디스크 I/O로 많은 데이터를 읽어올 수 있습니다. 대부분의 관계형 데이터베이스(MySQL InnoDB, PostgreSQL)는 B+Tree를 인덱스 구현에 사용합니다.

---

1. B-Tree 속성 (차수 t)

- 루트를 제외한 모든 노드: 최소 t-1개, 최대 2t-1개의 키
- 루트: 최소 1개의 키
- 내부 노드 키 k개 → 자식 k+1개
- 모든 리프 노드는 같은 깊이 (완전 균형)
- 키는 오름차순 정렬

---

2. C++ 구현 (핵심 연산)

#include <array>
#include <optional>

const int T = 3; // 최소 차수 (최대 키 수 = 2T-1 = 5)

struct BTreeNode {
    std::array<int, 2*T-1> keys;
    std::array<BTreeNode*, 2*T> children;
    int numKeys = 0;
    bool isLeaf = true;

    BTreeNode() { children.fill(nullptr); }
};

class BTree {
    BTreeNode* root = nullptr;

public:
    // 탐색
    std::optional<int> Search(BTreeNode* node, int key) {
        int i = 0;
        while (i < node->numKeys && key > node->keys[i]) i++;

        if (i < node->numKeys && key == node->keys[i])
            return key; // 찾음

        if (node->isLeaf) return std::nullopt; // 없음

        return Search(node->children[i], key); // 자식 탐색
    }

    // 노드 분할 (삽입 시 꽉 찬 자식 분할)
    void SplitChild(BTreeNode* parent, int i, BTreeNode* child) {
        auto* newNode = new BTreeNode();
        newNode->isLeaf = child->isLeaf;
        newNode->numKeys = T - 1;

        // 뒤쪽 T-1개 키를 새 노드로
        for (int j = 0; j < T-1; j++)
            newNode->keys[j] = child->keys[j + T];

        // 자식 포인터도 이동
        if (!child->isLeaf)
            for (int j = 0; j < T; j++)
                newNode->children[j] = child->children[j + T];

        child->numKeys = T - 1;

        // 부모에 중간 키 삽입
        for (int j = parent->numKeys; j >= i+1; j--)
            parent->children[j+1] = parent->children[j];
        parent->children[i+1] = newNode;

        for (int j = parent->numKeys-1; j >= i; j--)
            parent->keys[j+1] = parent->keys[j];
        parent->keys[i] = child->keys[T-1];
        parent->numKeys++;
    }
};

---

3. B-Tree vs B+Tree

항목	B-Tree	B+Tree
데이터 위치	내부/리프 노드 모두	리프 노드만
리프 연결	X	연결 리스트
범위 검색	O(N)	O(log N + k)
공간 효율	낮음	높음
사용 사례	파일 시스템	DB 인덱스

---

4. B+Tree 범위 검색

B+Tree 리프 노드 연결:
[1|2|3] → [4|5|6] → [7|8|9] → ...

범위 검색 [3, 7]:
1. 루트에서 3 위치 탐색 → O(log N)
2. 리프 포인터 따라 7까지 순회 → O(k)

// B+Tree 범위 검색
std::vector<int> RangeSearch(BPlusNode* root, int low, int high) {
    std::vector<int> result;

    // 시작 위치 탐색
    BPlusNode* leaf = FindLeaf(root, low);

    // 리프 연결 리스트 순회
    while (leaf != nullptr) {
        for (int i = 0; i < leaf->numKeys; i++) {
            if (leaf->keys[i] > high) return result;
            if (leaf->keys[i] >= low) result.push_back(leaf->keys[i]);
        }
        leaf = leaf->next; // 다음 리프로 이동
    }

    return result;
}

---

5. 데이터베이스 인덱스

5.1 클러스터드 인덱스

-- InnoDB: PK가 자동으로 클러스터드 인덱스
-- 데이터가 PK 순서로 물리적 배치
CREATE TABLE players (
    id INT PRIMARY KEY,  -- 클러스터드 인덱스
    name VARCHAR(50),
    score INT
);

-- PK 순서 조회: 매우 빠름 (물리적으로 연속)
SELECT * FROM players WHERE id BETWEEN 1000 AND 2000;

5.2 논클러스터드 인덱스

-- 별도 B+Tree 구조, 리프는 실제 행 포인터(PK) 저장
CREATE INDEX idx_score ON players(score);

-- score로 빠른 검색, 하지만 실제 데이터는 별도 조회 필요
SELECT * FROM players WHERE score > 1000;
-- → B+Tree로 score 검색 → PK 획득 → PK로 실제 행 조회

---

6. 인덱스 설계 원칙

-- ✅ 선택도(Selectivity) 높은 컬럼에 인덱스
-- unique한 값이 많을수록 효과적
CREATE INDEX idx_email ON users(email); -- 거의 unique

-- ✅ 복합 인덱스는 선택도 높은 컬럼을 앞에
CREATE INDEX idx_name_score ON players(name, score);
-- name + score 쿼리, name 단독 쿼리 → 사용 가능
-- score 단독 쿼리 → 사용 불가 (B-Tree 순서 규칙)

-- ❌ 카디널리티 낮은 컬럼 (gender, boolean)
-- 데이터의 50% 선택 → Full Scan이 더 빠를 수 있음

-- ✅ 커버링 인덱스 (쿼리 컬럼이 모두 인덱스에 포함)
CREATE INDEX idx_cover ON orders(user_id, amount, created_at);
SELECT user_id, amount FROM orders WHERE user_id = 1;
-- → 인덱스만으로 쿼리 해결 (테이블 접근 없음)

---

7. 페이지 크기와 트리 높이

디스크 페이지: 16KB (InnoDB 기본)
int 키 크기: 4B, 포인터: 8B
한 페이지당 키 수: 16KB / (4+8)B ≈ 1365개

1억 행 테이블의 B+Tree 높이:
  log_1365(100,000,000) ≈ 2.5 → 3단계

→ 1억 행에서 3번의 디스크 I/O로 조회

---

정리

• B-Tree: 디스크 최적화, 노드당 다수 키, 완전 균형
• B+Tree: 리프 연결로 범위 검색 최적화 → DB 인덱스 표준
• 클러스터드 인덱스: 데이터 물리 배치 = B+Tree 순서
• 논클러스터드 인덱스: 별도 B+Tree, 리프에 PK 저장
• 복합 인덱스: 왼쪽 접두사 규칙 주의

참고 자료

• Wikipedia — B+ tree
• MySQL Docs — InnoDB Index Types