Computer Science/Data Structure
🌲 B-Tree vs B+Tree 개념, 특징, 차이점, DB 인덱스에 사용되는 이유
소냐.
2024. 12. 20. 18:09
🌱 들어가기 전
데이터베이스 인덱스에 왜 B+Tree를 사용하는지 알아보기 위해,
이진탐색트리부터 B-Tree를 먼저 알아보고 B+Tree가 무엇이 다른지 차이점을 비교해서 정리해보고자 한다.
✅ 이진 탐색 트리(BST)
이진 탐색과 연결리스트를 결합한 자료구조로
모든 노드의 왼쪽 서브트리는 해당 노드의 값보다 작고, 모든 노드의 오른쪽 서브트리는 해당 노드의 값보다 크다는 특징을 가진다
✅ B-Tree
이진 탐색 트리(BST)를 일반화 시킨 트리 구조이다. 이진 탐색 트리는 하나의 노드가 최대 2개의 자식노드만 가질 수 있고, 하나의 노드에 1개의 데이터만 저장 가능하다. 하지만 하나의 노드가 최대 M개의 자식 노드를 가질 수 있도록 개념을 확장시켜 B-Tree 를 만들었다.
따라서 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가질 수 있으며, 최대 M개의 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 한다.
특징
- 자녀 노드의 최대 개수를 늘리기 위해서 부모 노드에 키를 하나 이상 저장
- 부모 노드의 키들을 오름차순으로 정렬
- 정렬된 순서에 따라 자녀 노드들의 키 값의 범위가 결정된다
B-Tree 파라미터
- M : 각 노드의 최대 자녀 노드 수
- M-1 : 각 노드의 최대 키 수
- M/2의 올림 : 각 노드의 최소 자녀 노드 수 (root 노드, leaf 노드 제외)
- (M/2의 올림)-1 : 각 노드의 최소 키 수 (root 노드 제외)
✅ B+Tree
B+Tree는 B-Tree 계열의 Balanced Tree의 종류 중 하나이다. MySQL의 InnoDB 스토리지 엔진은 주로 B+Tree를 사용한다. B+Tree는 데이터베이스 인덱스와 파일 시스템 사용에 더 적합할 수 있도록 만들어졌다.
특징
- B+Tree 모든 노드의 키는 항상 정렬된 상태를 유지한다(모두 오름차순 정렬)
- 새로운 데이터의 삽입 및 삭제가 비교적 간단하다
- 삽입 시에는 Leaf 노드에 새로운 데이터 추가
- 삭제 시에는 Leaf 노드에서 데이터 제거하며 B+Tree 균형을 유지
차별점(vs B-Tree)
- Leaf 노트는 서로 연결 리스트로 이루어짐 → 형제 노드끼리 옮겨가면 조회 가능
- Internal 노드에는 키만 저장됨 → 키를 사용해서 자식 노드의 메모리 상 위치를 판단
- 데이터 포인터도 없으며, 오로지 키만 저장된다
- 데이터를 찾기 위한 포인터도 Leaf 노드에만 있다
- Internal 노드의 크기를 줄여 메모리 사용이 효율적이다
- 실제 데이터는 Leaf 노드에만 저장되어 있다
B-Tree vs B+Tree
| B-Tree | B+Tree | |
| 검색 | 모든 노드(Internal + Leaf)에 키와 값이 함께 저장되어 있다 | Internal 노드에는 키만 저장 Leaf 노드에는 키와 값이 저장
|
| 포인터 사용 | Internal 노드의 포인터를 통해서만 Leaf 노드로 이동 가능함
|
Leaf 노드끼리 연결 리스트로 연결되어 있음
|
| 범위 쿼리, 범위 검색 | 범위 쿼리를 수행하려면 트리의 루프부터 리프 노드까지 이동하면서, 루트 노드, 인터널 노드에 있는 데이터까지 함께 조회해야 함 | 데이터는 리프 노드에만 존재함 범위 쿼리는 리프 노드를 시작으로 연결 리스트를 따라가면 모든 데이터를 조회할 수 있다 |
| 순차 탐색 및 정렬 | 순차 탐색이나 정렬을 위한 추가적인 알고리즘 필요 (ex. inorder traveral) → 보다 복잡 | 연결 리스트를 따라가면서 순차 탐색 용이 키들은 항상 정렬된 상태를 유지하면서 저장됨 |
| 메모리 사용 | 리프 노드와 내부 노드가 각각 데이터와 포인터까지 가지고 있어 B+Tree 보다 더 많은 메모리 공간 차지 | 데이터는 리프 노트에만 저장 Internal 노드는 키만 가지고 있으므로 메모리 효율이 좋다 |
✅ B+Tree가 DB 인덱스에 사용되는 이유
1. 메모리 효율
- BST와 비교하여 B-Tree 계열 트리 구조는 하나의 Block 단위의 저장 공간을 알차게 사용할 수 있다
- B-Tree 계열 트리 구조 중 B+Tree는 Leaf 노드를 제외하고는 데이터를 담지 않기 때문에 인터널 노드의 경우 한정된 메모리 안에 더 많은 키들을 수용할 수 있다
- 하나의 노드에 더 많은 키들을 저장하기 때문에 동일한 데이터 개수라면 트리의 높이는 더 낮아진다
2. 빠른 성능
- 트리의 높이가 낮고, 하나의 블록에 더 많은 데이터를 저장하기 때문에 Cache Hit를 높일 수 있을 뿐만 아니라, 범위 검색이나 범위 쿼리에도 큰 강점을 갖는다
- BST에 비해 secondary storage 접근을 적게 한다
- 또한 테이블 풀 스캔 시, B-Tree의 경우 데이터가 인터널 노드와 리프 노드에 퍼져있기 때문에 모든 노드를 탐색해야 한다.
- 하지만 B+Tree는 리프 노드에만 데이터가 존재하고, 존재하는 모든 데이터는 리프 노드에 있기 때문에 한 번의 선형탐색만 하면 되므로 매우 빠르다
728x90