B-trees: 캐시 효율성 및 데이터 구조 최적화

B-트리와 캐시 최적화: 데이터 구조 성능 극대화

현대 애플리케이션은 방대한 양의 데이터를 처리하는 문제에 끊임없이 직면하며, 데이터 구조의 성능은 매우 중요합니다. 레드-블랙 트리와 같은 전통적인 이진 탐색 트리는 대규모 데이터셋을 다룰 때, 특히 CPU 캐시 상호작용과 관련하여 상당한 단점을 보입니다. 이 글에서는 B-트리가 캐시 미스 문제를 어떻게 해결하며, 모든 데이터가 주 메모리에 상주할 때조차 고성능 데이터 저장 및 검색 시스템에서 왜 선호되는 선택지인지 탐구합니다.

전통적인 트리의 성능 문제

수백만 개의 레코드를 포함하는 데이터베이스에서 작업할 때, 이진 탐색 트리의 검색 작업은 수천 번의 CPU 사이클을 소모할 수 있습니다. 이러한 비효율성의 주된 원인은 데이터 지역성(data locality)이 좋지 않아 빈번한 캐시 미스가 발생하기 때문입니다. 이진 트리의 각 노드는 임의의 메모리 영역에 위치할 수 있으므로, 한 노드에서 다른 노드로 이동할 때마다 새로운 캐시 라인을 로드해야 합니다. 높이가 20단계인 트리(백만 개의 요소에 일반적)의 경우, 각 검색 작업은 최대 20번의 캐시 미스를 유발할 수 있습니다. 이는 주 메모리 접근 시간이 캐시 접근 시간보다 훨씬 느리기 때문에 데이터 접근 속도를 크게 저하시킵니다.

$ perf stat -e cache-misses,cycles ./db_query_rbtree
  Performance counter stats:
    18,500,000 cache-misses
   120,000,000 cycles

이 예시는 레드-블랙 트리가 쿼리를 처리할 때 1,850만 번의 캐시 미스를 발생시키고 1억 2천만 사이클을 소모하며, 이는 실시간 시스템에서는 용납할 수 없는 수준임을 보여줍니다.

B-트리 기본 원리: 다방향 접근 방식

B-트리는 이진 트리처럼 두 개가 아닌 여러 개의 자식을 가질 수 있는 자가 균형 탐색 트리입니다. B-트리의 핵심 특징은 각 노드에 저장되는 키의 수를 늘려 트리의 높이를 크게 줄이는 것입니다. 예를 들어, 차수(order) M의 B-트리는 노드당 최대 M-1개의 키와 M개의 자식을 가질 수 있습니다. 백만 개의 요소에 대해 차수 64의 B-트리는 높이가 약 3단계에 불과하지만, 이진 트리는 약 20단계가 필요합니다.

B-트리의 주요 특징:

각 노드는 최대 M-1개의 키를 포함합니다.
각 내부 노드는 최대 M개의 자식을 가집니다.
모든 리프 노드는 동일한 깊이에 있어 균형을 보장합니다.
각 노드 내의 키는 정렬되어 있습니다.

이러한 구조는 각 노드 내에서 이진 탐색을 가능하게 하는데, 이는 노드의 모든 키가 메모리에 연속적으로 저장되어 있어 매우 효율적입니다. 노드를 캐시에 로드하면 추가적인 주 메모리 접근 없이 모든 키에 접근할 수 있으므로 캐시 미스를 최소화합니다.

typedef struct btree_node {
    int num_keys;                    // 4 bytes
    int keys[BTREE_ORDER - 1];       // 252 bytes (63 keys for BTREE_ORDER=64)
    void *values[BTREE_ORDER - 1];   // 504 bytes
    struct btree_node *children[BTREE_ORDER];  // 512 bytes
    // Total: ~1272 bytes (fits into ~20 cache lines)
} btree_node_t;

int find_key(btree_node_t *node, int key) {
    // Binary search in a sorted array (캐시 친화적!)
    int left = 0, right = node->num_keys - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (node->keys[mid] == key) return mid;
        if (key < node->keys[mid]) right = mid - 1;
        else left = mid + 1;
    }
    return -1;  // Not found
}

캐시 효율성 메커니즘 및 벤치마크

B-트리의 핵심 장점은 캐시 효율성입니다. 노드에 접근할 때 단 한 번의 캐시 미스만 발생하며, 이로 인해 전체 노드가 CPU 캐시로 로드됩니다. 그 후, 노드 내 키에 대한 이진 탐색은 사실상 추가 지연 없이 진행됩니다. 따라서 B-트리에서 요소 검색 중 발생하는 캐시 미스 수는 트리의 높이와 같습니다. 높이가 3인 B-트리의 경우, 이는 검색 작업당 단 3번의 캐시 미스를 의미하며, 이진 트리에 비해 현저히 적습니다.

void* btree_search(btree_node_t *root, int key) {
    btree_node_t *node = root;
    
    while (node) {
        int i = 0;
        while (i < node->num_keys && key > node->keys[i]) {
            i++;
        }
        
        if (i < node->num_keys && key == node->keys[i]) {
            return node->values[i];
        }
        
        if (!node->children[0]) {
            return NULL;  // Not found
        }
        
        node = node->children[i]; // 자식 노드로 이동할 때 캐시 미스 발생
    }
    
    return NULL;
}

벤치마크 결과가 이를 뒷받침합니다. 백만 개의 요소와 10,000번의 무작위 검색 작업에 대해 차수 64의 B-트리는 레드-블랙 트리에 비해 6.7배 빠른 속도를 보였으며, 캐시 미스 수를 1,850만 번에서 280만 번으로 줄였습니다.

| :----------------- | :----- | :-------------------- | :----------- | :-------- |

| 레드-블랙 | 20 | 12,000 | 1,850만 | 1× |

| B-트리 (차수 16) | 5 | 3,200 | 480만 | 3.75× |

| B-트리 (차수 64) | 3 | 1,800 | 280만 | 6.7× |

| B-트리 (차수 256) | 2 | 1,200 | 190만 | 10× |

최적의 B-트리 차수 선택

B-트리의 차수 M을 선택하는 것은 트리의 높이와 노드 내 비교 횟수 사이의 절충을 포함합니다. 이상적인 차수는 프로세서의 캐시 라인 크기(일반적으로 64바이트)에 의해 결정됩니다. B-트리 노드는 이상적으로 하나 이상의 캐시 라인에 완전히 들어맞아야 합니다. 이는 노드를 로드할 때 캐시 미스를 최소화합니다. 예를 들어, 인메모리 B-트리의 경우 최적의 차수는 일반적으로 16-64 범위입니다. 디스크 I/O 비용이 훨씬 높은 디스크 기반 데이터베이스의 경우, 디스크 작업을 최소화하기 위해 차수를 훨씬 더 크게(128-512) 설정할 수 있습니다.

삽입, B+ 트리, 그리고 캐시-무지 구조

B-트리에 삽입할 때는 균형을 유지해야 하는데, 이는 오버플로우된 노드를 분할함으로써 달성됩니다. 노드가 최대 키 수에 도달하면 두 개로 분할되고, 중간 키는 부모 노드로 승격됩니다. 이 작업은 비교적 드물게 발생하므로 상각된 복잡도(amortized complexity)는 O(1)입니다.

void btree_insert(btree_node_t **root, int key, void *value) {
    btree_node_t *node = *root;

    if (node->num_keys == BTREE_ORDER - 1) {
        btree_node_t *new_root = create_node();
        new_root->children[0] = node;
        split_child(new_root, 0);
        *root = new_root;
    }

    insert_non_full(*root, key, value);
}

void insert_non_full(btree_node_t *node, int key, void *value) {
    int i = node->num_keys - 1;

    if (!node->children[0]) {  // Leaf node
        while (i >= 0 && key < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            node->values[i + 1] = node->values[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->values[i + 1] = value;
        node->num_keys++;
    } else {  // Internal node
        while (i >= 0 && key < node->keys[i]) {
            i--;
        }
        i++;

        if (node->children[i]->num_keys == BTREE_ORDER - 1) {
            split_child(node, i);
            if (key > node->keys[i]) i++;
        }

        insert_non_full(node->children[i], key, value);
    }
}

효율적인 범위 쿼리를 위한 B+ 트리

B+ 트리는 데이터베이스에 최적화된 B-트리의 변형입니다. B+ 트리에서는 모든 데이터(값)가 리프 노드에만 저장되며, 이 리프 노드들은 순차적인 리스트로 서로 연결되어 있습니다. 내부 노드는 검색을 안내하는 키만 포함합니다. 이는 범위 쿼리를 크게 가속화하는데, 범위의 시작점을 찾으면 전체 트리를 탐색할 필요 없이 리프 노드를 순차적으로 따라가기만 하면 되기 때문입니다. 이 구조는 MySQL InnoDB, PostgreSQL, SQLite를 포함한 대부분의 최신 관계형 데이터베이스에서 사용됩니다.

캐시-무지 B-트리

B-트리의 최적 차수는 아키텍처마다 다를 수 있는 캐시 라인 크기에 따라 달라집니다. 재귀적 레이아웃(예: van Emde Boas 레이아웃)을 기반으로 하는 캐시-무지 B-트리(Cache-oblivious B-trees)는 수동 튜닝 없이 모든 캐시 크기에 적응합니다. 구현은 더 복잡하지만, 광범위한 하드웨어 플랫폼에서 높은 성능을 제공합니다.