B-트리, B+트리, 2-3 트리, 2-3-4 트리

B 트리

말단 노드를 제외한 모든 노드는 2개 이상의 자식 노드를 가지는 트리

데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조
이진트리를 확장해서 더 많은 수의 자식을 가질 수 있게 일반화

- Balanced - Tree 의 일종
- B 트리는 하나의 노드에 여러 자료가 배치되는 트리구조
- 한 노드에 M개의 자료가 배치되면 M차 B 트리라고 함
- 데이터베이스와 파일시스템에 널리 사용
- 노드 내의 데이터는 오름차순으로 정렬
- 모든 말단 노드는 항상 레벨이 같음
- 새로운 값은 항상 말단노드에 삽입

B+ Tree

B-Tree와 유사하지만 연결리스트 내부의 데이터 탐색을 용이하게 하는 자료구조
모든 말단 노드는 연결리스트로 구현되어 있음
말단 노드가 아닌 노드들은 탐색을 위한 노드들로 키와 포인터만 가지고 있음
실제 DB의 인덱싱은 B+트리로 이루어져 있음

- 모든 key, data가 리프노드에 모든 data를 가지고 있음
- 모든 리프노드가 연결리스트의 형태를 띄고 있음
- 리프노드의 부모 key는 리프노드의 첫번째 key보다 작거나 같음 

 

2-3 트리

2 3 tree는 leaf 노드가 아닌 노드가 2개 또는 3개의 child를 가지는 노드로 이루어진 자료구조

- 2-노드와 3-노드만으로 구성되는 특수한 형태의 B트리

http://web.cecs.pdx.edu/~sheard/course/DepTypedProg/Notes/TwoThreeTreeAssignment.html

 

2-3-4 트리

2-3트리를 확장하여 4개의 자식을 가진 4-노드를 허용하는 탐색 트리

- 2-3-4트리는 2-3트리보다 삽입과 삭제가 용이

https://www.cs.cmu.edu/~tcortina/15-121sp10/homework9.html