- 이진 검색 트리를 일반화한 자료구조
- 2개 이상의 자식 가진 노드 허용
- 탐색에 O(logN)
- 대수확장성이란 특징으로 더 빠른 시간안에 많은 양의 데이터 빠르게 찾을 수 있는 구조
주요 특징
- 모든 리프 노드들은 같은 레벨에 존재 == 균형잡힌 트리 의미
- 차수는 노드가 가질 수 있는 최대 수 의미
- 예를 들어, 차수가 4면 각 노드는 최대 4개의 자식 가능
- 노드 내에 여러 키를 저장하고, 각 키는 자식 노드들 사이의 값을 구분하는 역할
- 예를 들어, 7과 16 사이에는 7이상 16 이하의 값들이 들어감
- 노드가 꽉 찼을 때, 새로운 항목 삽입 위해 노드를 분할. 반대로 삭제로 인해 노드 사용량이 줄어들면, 인접 노드와 병합 가능
작동 과정
- 루트 노드, 브랜치(내부) 노드, 리프 노드 로 구성(여기선 내부노드 없다고 가정)
- 핵심 원리는
- 요소들을 선형적으로 탐색하는 것이 아닌
- 트리라를 자료구조를 통해 “있을법한 노드”를 기반으로 찾고자 하는 요소를 빠르게 찾는 것
B 트리의 대수확장성
- B트리 이용한 인덱스가 효율적인 이유는
- BST로 O(logN)으로 탐색
- 대수확장성
- 트리 깊이가 리프 노드 수에 비해 매우 느리게 성장하는것 의미
- 4차 B 트리 경우 깊이 증가마다 최대 인덱스 항목이 4배씩 증가
- 예를 들면 깊이 10이면 100만개의 인덱스 가능한것임@
- 차수가 늘수록 깊이가 얕아짐