B-Tree

- 이진 트리를 확장해 더 많은 자식을 가질 수 있게 일반화 시킨 것
- 최악의 경우에도 O(log N) 보장

시뮬레이션: https://www.cs.usfca.edu/~galles/visualization/BTree.html

규칙

- 노드의 자료 수가 N이면 자식 수는 N+1이여야 함
- 각 노드의 자료는 정렬된 상태여야 함
- root는 적어도 2개 이상의 자식을 가져야 함
- M차 트리일 때, root와 leaf를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 함
- 모든 leaf가 같은 레벨을 가짐
- 입력 자료는 중복될 수 없음

M차 트리 - 최대 M개의 자식을 가지는 B Tree

B+ Tree

- B-Tree와 데이터의 연결리스트로 구현된 색인 구조
- index 부분과 leaf 부분으로 나뉨
- index 부분에는 다음 노드의 포인터 존재, leaf 부분에는 데이터의 연결 리스트 존재
- index 부분의 key 값은 leaf에 있는 key 값을 직접 찾아가는데 사용
- 대부분 DB에서 사용

시뮬레이션: https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

장점

- 블럭 사이즈를 더 많이 이용 가능 (key 값에 대한 하드디스크 액세스 주소가 없어서)
- leaf 노드끼리 연결 리스트로 연결되어 있어서 범위 탐색에 유리

단점

- B-Tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만,
  B+ Tree는 무조건 leaf 노드까지 내려가봐야 함

B-Tree & B+Tree