B Tree&B+ Tree

다원 탐색 트리(Multiway Search Tree)

정의 및 특징

• 트리의 노드가 최대 m-1개의 요소와 m개 이하의 서브 트리를 가질 수 있는 탐색 트리
• 트리의 높이를 줄이고 싶을 때 사용
• 각 노드는 최대 m개의 서브트리
• m개의 서브 트리를 가지는 노드는 m-1개의 요소를 가진다.
• 각 노드 안의 요소들은 오름차순으로 정렬

 

 B Tree

정의 

• M원 검색트리에서 균형 문제도 해결한 자료구조 => 데이터의 삽입, 삭제 시 균형을 맞추는 알고리즘을 수행 
• 최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 부름 

규칙

• 모든 리프 노드들 같은 레벨에 있다. 
• 모든 내부 노드는 최소 ⌈M/2⌉개의 자식을 가진다.
• 모든 노드들은 최대 M개의 자식을 가질 수 있다. 
• 리프가 아닌 모든 노드들은 최소 2개 이상의 자식을 가져야 한다. 
• k개의 자식을 가진 리프가 아닌 노드는 k-1개의 키를 가지고 있다.  

B Tree

 

키 삽입 과정 

1. 요소를 삽입할 단말 노드를 선택 후 키 삽입 
2. 노드가 가질 수 있는 키의 최대 개수를 초과할 경우, 분할 
3. 중앙값을 기준으로 분할 수행 
4. 중앙값을 부모 노드에 병합하고 왼쪽 키는 왼쪽 자식, 오른쪽 키는 오른쪽 자식으로 각각 연결
5. 부모 노드도 키의 최대 개수를 초과하지 않을 때까지 반복 

키 삭제 과정

• 삭제할 키가 리프에 있는 경우
  • 현재 노드의 키 개수가 최소 키 개수보다 크다면
    1. 단순 삭제
  • 왼쪽 또는 오른쪽 형제 노드의 키가 최소 키 개수 이상이라면
    1. 부모의 키 값으로 대체
    2. 최소키 개수 이상의 키를 가진 형제 노드가 왼쪽 형제라면 가장 큰 값을, 오른쪽 형제라면 가장 작은 값을 부모키로 대체
  • 왼쪽 또는 오른쪽 형제 노드의 키가 최소 키 개수이고, 부모노드의 키가 최소개수 이상이면
    1. 키를 삭제한 후, 부모의 키를 형제 노드와 병합 
    2. 부모노드의 키의 개수를 하나 줄이고, 자식 수도 하나 줄여 구조 유지
• 삭제할 키가 내부 노드이고, 노드나 자식에 키가 최소 키의 수보다 많을 경우 ...

 

B+ Tree

정의 및 특징

• 리프 노드에 새로운 data 값들이 들어가 있다. <=> B Tree는 각자 키마다 data 소유 
• 모든 리프노드가 연결리스트의 형태
• 데이터의 삽입/삭제 연산은 리프 노드에서만 발생

B+ Tree

 

 

Q: B 트리와 이진트리의 차이점? 

A: 차수를 M개로 확장하여 높이 문제와 균형 문제를 개선했다는 차이가 있다. 하나의 노드에 더 많은 키를 저장할 수 있다.

 

Q: B 트리와 B+ 트리의 차이점?

A: B 트리는 이진 트리를 확장해 모든 리프 노드들이 같은 높이를 갖도록 하는 트리이다. 노드는 정렬된 N개의 키를 가질 수 있고 그 경우 자식 노드는 N+1개가 된다. B+ 트리는 리프 노드에만 데이터가 있고, 각 리프 노드가 연결 리스트 형태를 띄어 선형 검색이 가능하다. 

 

Q: 검색 자동완성을 어떻게 구현할 수 있을까?

A: 트라이 자료구조를 사용한다. 

 

 

 

참고

https://philosophy-coding.tistory.com/51?category=1142866

B 트리와 B+ 트리

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Tree

velog