자료구조:B-tree, B+tree, B* tree

B-tree

이진탐색 트리(BST)가 한쪽으로 치우칠 경우 최악의 시간 복잡도는 O(n)이 된다.
따라서, 이 문제를 해결하기 위해 균형을 맞추도록 설계한 트리 중하나가 B-tree이다.

인덱스를 만들기 위해 쓰는 자료 구조이다.

CPU보다 느린 디스크 I/O의 문제점을 개선하기 위해 만든 자료구조이다.

• 각 노드는(루트를 제외) 최대 m개 최소 (m/2)개의 subTree를 가져야한다.
  - 적어도 반 이상은 key로 채워져서 효율적으로 분배되도록 하는 것이다.
• 모든 리프노드는 같은 level에 있어야한다.
• 리프노트의 key 값의 갯수는 최소 (m/2)-1 개 최대 m-1개이다.

B+tree

• 리프노는 데이터, 그 외에 노드는 데이터를 찾기 위한 key와 포인터로 이루어진다.
• B tree의 보조연산을 보완하기 위해 변영한 트리로 보조연산을 줄인다는 특징이다.
• B-tree에 비해 공간 활용도가 높다.
• 노드가 꽉 차면 분열하지 않고 형제 Node로 재 배치한다.(인접 노드가 꽉 찰 때까지 지연가능하다.

B*tree

• index 부분과 순차 데이터 부분으로 구성한다.
• 모든 데이터를 가진 Node들이 리프노드의 마지막 높이에 존재하도록 유지한다.
• 연결리스트로 순차적으로 검색한다.

출처:
https://www.youtube.com/watch?v=b2Ly05Fn7ks&t=3501s
https://ju-hy.tistory.com/106
https://jingonpark-gameclient.tistory.com/50