[자료구조] B-tree, B+tree 이론 정리

B-tree

 "데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다."

 

정리하자면, B-tree는 Binary search tree와 유사하지만, 한 노드 당 자식 노드가 2개 이상 가능하다 라고 할수있다.

 

여기서 먼저 트리구조에 대해 알아보자.

트리 구조는 꼭 데이터베이스에 한정하지 않더라도 시스템 세계에서는 데이터를 유지하기 위해 자주 사용하는 구조이다. '탐색' 시, 단시간 내에 실행할 수 있기 때문이다. 

 

B-tree의 핵심은 데이터가 정렬된 상태로 유지되어 있다는 것이다.

출처:https://zorba91.tistory.com/293

 

그림에 표시된 사각형으로 표시된 한 개 한 개의 데이터를 '노드(Node)'라고 한다.

 

가장 상단의 노드를 '루트 노드(Root Node)', 중간 노드들을 '브랜치 노드(Branch Node)', 가장 아래 노드들을 '리프 노드(Leaf Node)'라고 한다. (B-tree가 되려면 위 그림에 맨왼쪽 Branch에 Leaf Node 하나가 추가되어야함) 

 

B-tree의 경우 key와 data를 브랜치 노드와 리프 노드에 담을 수 있다. 따라서 풀 스캔을 위해 모든 노드를 탐색해야 한다.

---

Balanced Tree

B-tree는 Balanced Tree의 한 종류인데, Balanced Tree는 노드 삽입 및 삭제 시 스스로 균형을 맞춰주는 트리를 말한다. 기존 이진 트리의 문제점은 좌우 균형이 맞지 않다는 것이었는데, 트리가 좌우 불균형 하면 높이가 커서 검색하는데 상당히 비효율적일 수 있다. (최악의 경우엔 선형검색과 같은 O(N)의 시간복잡도를 가짐) 이를 위해 균형적으로 트리를 만들어 주면, 어느 경로를 가더라도 높이가 같다. (시간복잡도 O(logN))

 

Balance 트리에는 AVL 트리, Red-Black Tree, B-Tree가 있다. 

---

균형트리

B-tree는 균형트리인데, '균형 트리'란 루트로부터 리프까지의 거리가 일정한 트리 구조를 뜻하는 것으로, 트리 중에서 특히 성능이 안정화 되어있다. 

출처:https://zorba91.tistory.com/293

---

B+tree

B+tree는 B-tree의 확장 개념으로, B-tree와 달리 브랜치 노드에는 key만 담고, 리프 노드에만 key와 data를 담을 수 있으며, 각 리 노드끼리 Linked list로 연결되어 있다.

 

 따라서 B+tree는 아래와 같은 장점을 갖는다.

 

1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다. 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다.(cache hit를 높일 수 있음)

 

2. 풀 스캔 시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 되기 때문에 B-tree에 비해 빠르다.(리프노드에서 선형탐색)

---

B-tree Vs B+tree 

출처:https://seunggi92.tistory.com/39

 

 

 

 

 

📗참고사이트

[MySQL] B-tree, B+tree란? (인덱스와 연관지어서)