B-tree와 B+ tree란 무엇이며, 데이터베이스는 왜 이를 사용하나요?

Question

Accepted Answer

**B-tree**는 각 노드가 **많은 key**를 담고 **많은 자식**을 갖는(높은 *팬아웃(fanout)*) 자가 균형 탐색 트리입니다. 이는 트리를 **얕게** 유지하여 **디스크 읽기** 횟수를 최소화하며, 이것이 바로 데이터베이스와 파일 시스템에 필요한 것입니다. ## 높은 팬아웃이 binary tree를 이기는 이유 ```text 1,000,000개 key에 대한 Binary BST -> 높이 ~20 (디스크 탐색 20회) B-tree, 노드당 100개 key -> 높이 ~3 (디스크 탐색 3회) 각 노드 = 하나의 디스크 블록/페이지 읽기. ``` ## 구조 (B-tree 차수 4) ```text [ 17 | 35 ] / | \ [4|9|12] [20|28] [40|50|60] 각 노드가 많은 key를 채움 -> 적은 레벨 ``` ## B+ tree 개선 **B+ tree**에서는 *모든 값이 리프에 존재*하고 리프들이 **연결(linked)**되어 있어, 범위 스캔이 리프들의 linked list를 따라 걷습니다. `WHERE age BETWEEN 20 AND 40` 같은 질의에 이상적입니다. ```text 내부 노드: key만(라우팅) 리프: [..]<->[..]<->[..] <- 빠른 범위 스캔을 위해 연결됨 ``` ## 복잡도 | 연산 | 시간 | 디스크 I/O | |---|---|---| | 검색 | O(log n) | O(높이) | | 삽입 / 삭제 | O(log n) | O(높이) | | 범위 스캔 | O(log n + k) | 순차적 리프 | ## 왜 중요한가 디스크와 SSD 접근은 메모리보다 수십 배 느리므로, 중요한 척도는 비교 횟수가 아니라 **I/O 횟수**입니다. 높은 팬아웃은 트리를 단 몇 레벨 깊이로 유지하여 I/O를 대폭 줄입니다. 이것이 거의 모든 관계형 데이터베이스 인덱스(와 많은 파일 시스템)가 binary search tree가 아니라 B+ tree로 만들어지는 이유입니다.

연산	시간	디스크 I/O
검색	O(log n)	O(높이)
삽입 / 삭제	O(log n)	O(높이)
범위 스캔	O(log n + k)	순차적 리프