B 트리 (B-트리 B+트리)

대용량 데이터를 디스크에서 효율적으로 관리하기 위한 AVL트리 자료구조
하나의 노드 에 많은 데이터 저장 → 트리 높이 낮춤 → 디스크 접근 횟수 낮춤
데이터베이스 인덱스 와 파일 시스템의 핵심 기술
기존의 AVL트리나 이진트리 의 경우엔 렘 에선 빠르지만 디스크에선 여러번 접근하는 비싼 작업 해야함
디스크 접근 (I/O) 횟수 자체를 줄여야 함 → 트리의 높이를 최대한 낮춘다 → 트리를 최대한 옆으로 넓게 펴고, 각 노드에 많이, 자식 많이
규칙 1: 모든 리프 노드는 같은 높이에 있다.
- 어떤 데이터 검색해도 항상 비슷한 시간 소요
규칙 2: 각 노드는 m/2 이상 m 이하의 자식을 가질 수 있다. (단, 루트 노드는 예외)
- m/2 를 최소 차수라고 하며, 노드가 항상 절반 이상 채워지게
규칙 3: 노드에는 k개의 키가 있다면, k+1개의 자식 포인터를 가진다.
- 키들을 정렬된 상태로 저장

특징	B-트리	B+ 트리
데이터 저장 위치	모든 노드(내부, 리프)에 (키, 데이터) 쌍을 저장	오직 리프 노드에만 (키, 데이터) 쌍을 저장
내부 노드의 역할	키와 데이터, 자식 포인터 저장	경로 탐색을 위한 키(인덱스)와 자식 포인터만 저장
리프 노드 구조	독립적으로 존재	모든 리프 노드가 연결 리스트(Linked List)로 서로 연결됨
주요 사용 사례	특정 키 하나를 찾는 점 질의(Point Query)에 유리	특정 범위의 데이터를 모두 찾는 범위 질의(Range Query)에 압도적으로 유리

시스매