B Tree & B+ Tree

B Tree 자료구조

• 이진 탐색 트리와 유사한 자료구조
• 자식 노드를 둘 이상 가질 수 있고 Balanced Tree 라는 특징이 있다.
  ✅ 탐색 연산에 있어 O(log N)의 시간 복잡도를 가진다.
• 모든 노드들에 대해 값을 저장하고 있으며 포인터 역할을 동반한다.

규칙

1. 노드의 자료수가 N이면, 자식 수는 N+1이어야 한다.
2. 각 노드의 자료는 정렬된 상태여야 한다.
3. 루트 노드는 적어도 2개 이상의 자식을 가져야 한다.
4. 루트 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다.
5. 외부 노드로 가는 경로의 길이는 모두 같다.
6. 입력 자료는 중복될 수 없다.

데이터 삽입

• 추가는 항상 리프 노드에 한다.
• 노드가 넘치면 가운데 key를 기준으로 좌우 key들을 분할하고 가운데 key는 승진한다.
  📢 노드가 넘치는 경우 : M차 B Tree에서 각 노드는 최대 M-1개의 key를 가질 수 있는데 데이터를 삽입하는 과정에서 이를 위반한 것

출처 : https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC

 

B+ Tree 자료구조

• B Tree를 개선한 형태의 자료구조
• 값을 리프 노드에만 저장하며 리프 노드들끼리는 연결 리스트로 연결되어 있다.
  ✅부등호문 연산에 대해 효과적이다.
• 리프 노드를 제외한 노드들은 포인터의 역할만 수행한다. 
  ✅ 중간 노드에는 key만 두고 value는 담지 않는다.

장점

1. 블럭 사이즈를 더 많이 이용할 수 있다.
   → key 값에 대한 하드디스크 액세스 주소가 없기 때문
2. 리프 노드끼리 연결 리스트로 연결되어 있어서 범위 탐색에 매우 유리하다.

단점

1. B Tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+Tree는 무조건 리프 노드까지 내려가야 한다.

 

[참고]
https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/B%20Tree%20%26%20B%2B%20Tree.md

tech-interview-for-developer/Computer Science/Data Structure/B Tree & B+ Tree.md at master · gyoogle/tech-interview-for-develop

 

https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC

B-트리(B-Tree)란? B트리 탐색, 삽입, 삭제 과정