B-트리 시각화
데이터베이스 인덱싱의 핵심인 B-트리의 삽입·삭제·검색을 단계별로 학습하세요
자료구조★★★
속도
1 / 1노드 수: 0키 수: 0높이: 0
연산 선택
max 3 keys/node
현재 노드검색 성공분할 중승격 중
B-트리가 노드 분할로 어떻게 균형을 유지하는지 관찰하세요.
비교
자식 이동
삽입
분할
승격
값을 입력하고 실행을 눌러 시작하세요.
B-트리란?
한 노드에 여러 키를 저장하는 자가균형 다진 탐색 트리입니다. 디스크 I/O를 최소화하도록 설계되어 데이터베이스와 파일시스템 인덱싱의 표준입니다.
사용 방법
- 1차수(t)를 설정하세요 — 각 노드에 최대 2t-1개 키 저장
- 2값을 입력하고 삽입하면 분할 과정을 관찰할 수 있습니다
- 3검색 버튼으로 키를 찾는 경로를 확인하세요
- 4노드가 가득 차면 분할(split)이 발생합니다
동작 원리
- 1삽입 시 리프 노드에 키를 추가합니다
- 2노드가 가득 차면(2t-1개 키) 중간값을 부모로 올리고 좌우로 분할합니다
- 3검색은 루트부터 키 범위를 비교하며 자식 노드로 내려갑니다
- 4삭제 시 키가 부족한 노드는 형제에서 빌리거나 병합합니다
실무 활용
- •MySQL InnoDB, PostgreSQL의 인덱스 구조(B+트리 변형)
- •파일시스템(NTFS, ext4, HFS+)의 디렉토리 인덱싱
- •MongoDB, CouchDB 등 NoSQL DB의 인덱스
- •대용량 키-값 저장소(LevelDB, RocksDB)의 SSTable 인덱스
비슷한 알고리즘
- •B+트리 — 모든 데이터를 리프에 저장하고 리프를 연결 리스트로 연결, 범위 검색에 최적
- •레드-블랙 트리 — 이진 트리로 메모리 기반, B-트리는 디스크 기반에 적합
- •LSM 트리 — 쓰기 최적화 구조로 B-트리보다 순차 쓰기가 빠름
학습 팁
- •차수 2(2-3-4 트리)부터 시작하여 분할 패턴을 익히세요
- •레드-블랙 트리와 2-3-4 트리의 대응 관계를 살펴보세요
- •분할 시 중간값이 올라가는 과정에 주목하세요
자주 묻는 질문
Q. B-트리와 B+트리 차이?
A. B+트리는 데이터를 리프에만 저장하고 리프를 연결하여 범위 검색이 빠릅니다.
Q. 차수(t)는 어떻게 정하나?
A. 디스크 블록 크기에 맞춰 정합니다. 보통 수백~수천으로, I/O 한 번에 한 노드를 읽습니다.