B - Tree & B + Tree

B-Tree

• 하나의 노드에 여러 자료(데이터)가 배치되는 트리 구조
• 스스로 균형을 맞추는 트리 --> 최악의 경우에도 O(logN)의 검색 성능을 보인다.
• 한 개의 노드에 M개의 자료가 배치되면 M차 B 트리라 한다 
• 규칙

      - 노드의 자료수가 n이라면, 자식 수는 n+1

      - 각 노드의 자료는 정렬된 상태

      - root노드는 적어도 2개 이상의 자식을 가짐

      - root노드 제외 모든 노드는 적어도  M/2개의 자료를 가짐

---

B+ Tree

• 색인 구조에서 순차 접근에 대한 문제의 해결책으로 제시
• key값이 leaf node와 leaf의 부모 노드에 공존
• B-Tree의 변형 구조로 index부분과 leaf노드로 구성된 순차 data부분으로 이루어짐
• index 부분의 key값은 leaf에 있는 key값을 직접 찾아, 모든 key 값은 leaf노드에 나열
• leaf노드는 순차적으로 linked list를 구성 --> 임의 접근 & 순차 접근 가능
• 장점 

      - key값에 대한 harddisk 엑세스 주소가 없기 때문에 노드 사이즈를 더 많이 이용 가능

      - leaf 노드끼리 limked list로 연결되어 있어서 시퀀셜한 레인지 탐색에 매우 유리함 

• 단점

      - 무조건 leaf 노드까지 가야 함 

 

• 예시

  

  B+트리의 예시 그림

               - 리프 노드에서만 레코드 포인터를 가진다.

               - 리프 노드에 모든 key값이 존재한다.

               - 리프 노드가 linked list형태임을 알 수 있다.  

• 삽입

     - 빈자리가 있을 경우: 그냥 삽입

     - 빈자리가 없을 경우: 노드를 분리하고 중간 값을 가진 노드를 부모 노드에 삽입

   

출처: 아래있다.

• 삭제: leaf 노드에서만 key값을 삭제

      - 형제 노드 재분배 가능: 분배 후, 작은 키 값을 삭제한 노드 위치에 둠

      - 형제 노드 재분배 불가능: 삭제할 키 값의 leaf 노드와 형제 노드를 병합

 

---

 

---

출처:

https://wangin9.tistory.com/entry/B-tree-B-tree

https://velog.io/@seanlion/btree

https://goodgid.github.io/FP-B+-Tree/

B트리,B+트리, B*트리 개념 정리