자료구조 강의 12화 :: m원 탐색 트리, B 트리, B* 트리, B+ 트리

자료구조 12화를 듣고 배운내용

 

 

KEYWORDS

• m원 탐색 트리: 트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리
  
  
• B 트리: 인덱스 구조를 구현하는데 가장 일반적으로 사용하는 차수가 m인 트리
  
  
• B*: 노드의 약 2/3이상이 차야하는 B트리
  
  
• B+: 모든 키 값이 잎 노드에 있고, 그 키 값에 대응하는 실제 데이터에 대한 주소를 잎 노드만 가지고 있는 트리
  인덱스된 순차 파일을 구성하는데 사용되는 트리

 

 

이진 탐색 트리의 단점?

노드의 개수가 많아지면 트리의 높이가 커진다.

m원 탐색 트리로 만들면 높이가 낮아진다.

 

 

m원 탐색 트리

m개 이하의 자식을 가질 수 있는 트리

높이를 줄이기 위해 집중한 트리

이진 탐색 트리보다 높이가 낮다

 

 

B 트리

m원 탐색 트리에서 균형을 잡은 트리

인덱스 구조 구현하는데 가장 일반적인 방법.

루트와 노드를 제외한 트리의 각 노드는 최소 m/2개의 서브트리를 갖는다

트리의 루트는 최소 2개의 서브트리를 갖는다.

트리의 모든 잎 노드는 같은 레벨에 있다.

 

삽입 연산시,

노드가 꽉 찬 경우 분리해서 키값과 포인터를 재분배해야 한다.

 

 

B* 트리

노드의 약 2/3 이상 채워지는 B 트리

노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치해서 다른 형제 노드로 옮긴다.

 

 

B+ 트리

인덱스된 순차 파일을 구성하는데 사용된다.

데이터를 차례로 처리하는 순차처리와 특정 데이터를 찾아 처리할 때 효율적이다.

 

모든 키 값은 잎 노드에 있다,

중간 노드는 잎 노드까지 찾아가기 위한 주소 역할만 한다.

 

 

search by Clem Onojeghuo #unsplash