반응형
✅ B-Tree는 Binary Tree(이진트리)와 “비슷하지만 더 일반화된 구조”
| 구분 | Binary Tree | B-Tree (Balanced Tree) |
| 노드당 자식 수 | 최대 2개 | 여러 개 (예: 50개 이상도 가능) |
| 저장 위치 | 메모리 | 디스크 페이지 단위 |
| 탐색 효율 | O(log n) | O(log₍ₘ₎ n), m=자식수 |
| 사용 용도 | 알고리즘 교재, 메모리 내 구조 | 데이터베이스, 파일시스템 |
🧩 정리하자면
- “B-Tree”는 Binary Tree의 확장 버전이에요.
- DB는 디스크 I/O를 최소화해야 하므로, 한 노드에 여러 키를 묶어둡니다.
- MySQL(InnoDB)은 B+Tree라는 변형을 실제로 사용합니다.
- 모든 데이터는 리프 노드(leaf)에만 저장
- 리프 노드끼리 링크드리스트로 연결되어 있어 범위 검색이 빠름 (BETWEEN, LIKE 'A%' 등)