[자료구조] B- 트리란?

B- tree가 무엇인가?

자료구조 중 하나

이진트리와 다르게 하나의 노드에 최대 M개의 자식을 가지는 트리

 

예를들어 값이 [10, 20]이 있으면

10보다 작은 서브트리, 10과 20 사이의 서브트리, 20보다 큰 서브트리 이렇게 3개의 자식이 생기는 트리가 B-트리이다.

 

삽입의 경우 M개의 제한을 걸어두고 값이 M개 이상이 되면 (노드는 최대 M-1개 까지 값을 가질 수 있다) 분할이 이루어진다

분할 과정은 가운데 값이 부모 노드로 올라가서 합쳐지는 방식으로 부모노드도 초과할 경우 계속 올라가는 방식으로 삽입이 진행된다

삭제는 더 어렵다, 자세한 것은 블로그 참조

 

[자료구조] 그림으로 알아보는 B-Tree

[자료구조] 그림으로 알아보는 B-Tree

 

B- 트리의 업그레이드

B- 트리는 M개의 자식을 가지게 되면서 이진트리의 상위호환이 되었지만 구조를 유지하기 위해서 추가적인 연산이 수행되거나 새로운 노드가 생성된다는 단점이 있다.

 

그래서 이러한 연산과 추가적인 노드 생성을 최소화하기 위해 몇 가지 규칙이 추가된 것이 B* tree이다

 

또한 B- 트리의 경우 탐색을 위해 노드를 찾아 이동해야 한다는 단점이 있었다

이러한 단점을 해결하고자 B+ 트리이고 기본적인 아이디어는 같은 depth까지 이동 후 같은 레벨의 노드를 연결리스트로 연결시켜 탐색한다라는 아이디어이다.

부모 자식을 왔다갔다 하면서 찾는 B- 트리보다는 훨씬 유리하다

 

있을지 없을지 모르는 탐색을 하는 B- 트리보다는 무조건 존재하는 B+ 트리가 효율적이기 때문에 오늘날 데이터베이스들은 B+ 트리 구조를 채택한다.

 

[자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree

[자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree