[DataBase] B-tree 와 B+tree에 대하여

B+ tree는 단순한 이진 탐색 트리(binary search tree)와는 달리, 대용량 데이터를 디스크에 효율적으로 저장하고 빠른 검색 속도를 제공하는데 최적화된 구조입니다.

실제로 MySQL의 InnoDB 스토리지 엔진은 이 B+ tree를 기반으로 클러스터링 인덱스(Clustered Index)를 구성하여, 데이터가 정렬된 상태로 저장되고 검색 시 성능을 극대화할 수 있도록 돕습니다.

 

우선 B+ tree에 대해 알기전에 기본이 되는 B-tree에 대해 먼저 알아보겠습니다.

 

B-Tree

B-트리는 이진 트리를 일반화한 형태로, 각 노드가 최대 N개의 자식 노드를 가질 수 있도록 확장된 균형 잡힌 트리입니다. 이를 통해 데이터의 삽입, 삭제, 검색을 효율적으로 수행할 수 있습니다. 하지만 단순히 자식 노드 수를 늘리는 것뿐만 아니라, 자식 노드와 키(key)를 어떤 기준으로 저장할지에 대한 규칙이 필요합니다. 이 규칙은 B-트리의 차수(Order)인 M을 기준으로 정의됩니다.

Balanced Tree -> 모든 리프노드들이 같은 레벨이기에 조회성능이 LogN으로 일정하다.

B-트리의 주요 파라미터

B-트리의 구조를 이해하려면 아래의 파라미터와 그 의미를 알아야 합니다:

• M: 각 노드가 가질 수 있는 최대 자식 노드 수로, 이를 "M차 B-트리"라고 부릅니다.
• M-1: 각 노드가 가질 수 있는 최대 키(key) 수입니다. 키는 자식 노드 사이의 경계를 구분하는 값으로 사용됩니다.
• ⌈M/2⌉: 각 노드가 유지해야 하는 최소 자식 노드 수입니다. 단, 루트 노드와 리프 노드는 예외로 처리될 수 있습니다. (⌈x⌉는 x를 올림한 값)
• ⌈M/2⌉ - 1: 각 노드가 유지해야 하는 최소 키(key) 수로, 루트 노드를 제외한 모든 노드에 적용됩니다.

규칙

1. internal 노드의 key 수가 x개 라면 자녀 노드의 수는 언제나 x+1개
2. 각 노드가 최소 하나의 key는 가지기에 몇 차 B tree 인지와 상관없이 internal 노드는 최소 두개의 자녀는 가진다.
3. key는 정렬되어있다.(오름차순)
4. 모든 Leaf 노드들은 같은 레벨에 있다.

B+ Tree

B+트리는 모든 데이터가 리프 노드에 저장되는 균형 잡힌 트리입니다. 내부 노드는 오직 인덱스로만 사용되며, 리프 노드는 연결 리스트

서로 연결되어 있습니다. 이러한 구조 덕분에 범위 쿼리와 순차적 데이터 접근이 매우 빠릅니다. 루트 노드는 값의 범위를 나타냅니다.

즉, B-Tree와의 차이점은 데이터는 전부 리프노드에 있으며 internal node는 인덱스로만 사용된다 라는 차이가 있습니다.

 

 

 

 

 

참고:

https://www.youtube.com/watch?v=bqkcoSm_rCs

https://www.youtube.com/watch?v=H_u28u0usjA

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-Plus-Tree

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