[DB] B-Tree vs B+Tree

B-Tree

B-트리는 이진 탐색 트리를 확장한 형태로, 하나의 노드가 여러 개의 키를 가질 수 있는 균형 트리로 모든 리프 노드가 동일한 레벨에 존재하며, 각 노드는 자식 노드에 대한 포인터를 포함. 이러한 구조는 데이터베이스와 파일 시스템에서 주로 사용

 

b-tree

B-Tree의 특징

• 다중 키 저장: 각 노드는 여러 개의 키를 포함하며, 키들은 오름차순으로 정렬
• 자식 노드 분할: 노드의 키 개수가 N개라면, 해당 노드는 최대 N+1개의 자식 노드를 가질 수 있습니다.
  • 예를 들어서, 부모 노드에 55, 65라는 2개의 값이 저장되어 있다면, 자식 노드는 아래 3가지 케이스로 값을 구분해서 저장 가능
    1. 55보다 작은 값
    2. 55초과, 65 미만의 값
    3. 65보다 큰 값
• 균형 유지: 모든 리프 노드는 동일한 레벨에 위치

 

B-Tree 장점

• 낮은 트리 높이: 한 노드에 여러 키를 저장하므로, 트리의 높이가 낮아집니다. 트리의 레벨이 낮아지므로, 탐색 시 거쳐야 하는 노드 수를 줄여줍
• 효율적인 범위 검색: 키들이 정렬되어 있어 범위 검색이 용이

 

B-Tree의 탐색 시간 복잡도는 :O(logₘ N) <*m은 자식의 수>

 

 

B+Tree

B-Tree에서 검색 성능을 한층 개선한 자료구조가 바로 B+Tree. 대표적으로 InnoDB엔진에서 Index를 관리할 때 B+Tree를 사용

(MySQL, Postgress, Oracle 등 현대 DB 엔진에 해당함, 이전 MyISAM..)

• B+ Tree 는 B-Tree보다 범위 검색에 유용
• B-Tree와 차이는, 리프 노드(Leaf Node) 간의 연결성이 추가된 자료 구조로 Leaf Node에만 값을 저장하는 특성 (B-Tree는 모든 노드에 값들)
  • 하나의 노드 위치를 알게 되면 Leaf 노드 간의 연결성을 통해서 나머지 값을 탐색할 수 있는 것.
    • 예를 들어, 43의 위치를 알게 되면 그 후부터는 현재 Leaf노드의 오른쪽 방향만 빠르게 탐색해서 52의 위치를 알 수 있는 것

 

B-Tree에 비해 약점은?

• 메모리 효율성과, 생성 및 삭제의 효율성이 떨어짐
  • B-Tree의 경우, 리프노드 간 연결을 나타내는 데이터도 추가적으로 관리해야하기에 오버헤드 발생