B-tree, B+tree

균형 이진 트리

- 리프 노드들의 레벨 차이가 최대 1레벨까지만 나는 트리, 검색할 때 O(logN) 시간 복잡도 유지(균형이 깨지면 별도 로직을 통해 다시 균형 유지)

- B-tree 처음 생성 당시에는 균형 트리이지만, 테이블 갱신(INSERT, UPDATE, DELETE)의 반복을 통해 서서히 균형이 꺠지고, 성능도 약화된다.

- 어느 정도 자동으로 균형을 회복하는 기능이 있지만, 갱신 빈도가 높은 테이블에 작성되는 인덱스 같은 경우 인덱스 재구성을 해서 트리의 균형을 되찾는 작업이 필요하다.

- AVL 트리, 레드 블랙 트리, B-tree, B+tree 등에서 사용

 

B-tree

- 데어베이스 인덱스, 파일 시스템, 파일 시스템 캐시 등에서 널리 사용되는 트리 자료구조

- 이진 트리의 확장, 하나의 노트에 자식 2개 이상

- 내부 노드에 key와 data를 담을 수 있다.

B-tree 조건

1. 모든 노드들은 최대 m개의 자식을 가질 수 있다.
2. k개의 자식을 가진 리프가 아닌 노드는 k-1개의 키를 가지고 있다.
3. 모든 내부 노드는 최소 [m/2]개의 자식을 가져야 한다.
4. 모든 리프 노드들은 같은 레벨에 있어야 한다.
5. 리프가 아닌 모든 노드들은 최소 2개 이상의 자식을 가져야 한다.

B-tree

 

데이터양에 따른 처리시간 그래프

풀 스캔이 테이블 크키에 비례하는 형태로 실행 시간이 늘어가는 데에 비해 인덱스를 사용할 경우 실행 시간의 저하는 보통 원만한 곡선을 그리게 된다.

 

B+tree

- B-tree를 개선

- 모든 리프 노드들은 Linked 리스트 형태로 이루어진다.

- 실제 데이터는 리프 노드에만 저장, 내부 노드들은 단지 키만 가지고 있고 올바른 리프 노드로 연결해주는 라우팅 기능을 한다.

- B+tree는 중복 키를 가진다. -> 내부 노드들이 데이터를 가지고 있기 때문에 리프 노드들이 키와 데이터를 모두 가지고 있음.

 

B+tree

 

B+tree의 장점

1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에 메모리를 더 확보함으로써 더 많은 key들을 수용할 수 있다.
   하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다.(cache hit를 높일 수 있음)
2. 풀 스캔시, B+tree는 리프 노드에 데이터가 모두 있기 때문에 full scan시 한 번의 선형탐색만으로 빠르게 확인할 수 있다.
   (B-tree는 모드 노드를 탐색해야 한다)

B+tree의 단점

1. B-tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+tree는 무조건 리프 노드까지 내려가 봐야 한다.

활용사례

ex) InnoDB에서 사용된 B+tree

B+Tree Structure

- 같은 레벨의 노드끼리는 Double LinkedList 사용

- 자식 노드로는 Single Linked List로 연결

- key의 범위마다 찾아가야할 페이지 넘버(포인터)가 있는데, 해당 페이지 넘버를 통해 곧바로 다음 노드로 넘어감.

- 리프 노드에서 디스크에 존재하는 데이터의 주소값을 구할 수 있고, Linked List를 통해 탐색도 가능

 

구분	B-tree	B+tree
주요 특징	모든 내부, 리프 노드들이 데이터를 가진다.	단지 리프노드만 데이터를 가진다.
검색	자주 access 되는 노드를 루트 노드 가까이 배치할 수 있고, 루트 노드에서 가까울경우, 브랜치 노드에도 데이터가 존재하기 때문에 빠름.	리프 노드까지 가야 데이터 존재
키 중복	없음	있음
트리의 높이	높음	낮음(한 노드 당 key를 많이 담을 수 있음)
풀 스캔시, 검색 속도	모든 노드 탐색(상대적으로 느림)	리프 노드에서 선형 탐색(상대적으로 빠름)
사용	데이터베이스, 검색엔진	멀티레벨 인덱스, DB 인덱스

 

 

 

B+Tree가 DB 인덱스에 사용되었을 때, 더 좋은 점

1. 한정된 메모리 안에 더 많은 key들을 수용할 수 있다. -> 동일한 데이터 개수라면, 트리의 높이는 더 낮아진다.
2. cache hit를 높일 수 있을 뿐만 아니라, 범위 검색이나 범위 쿼리에도 큰 강점을 갖고 있으며, 상대적으로 굉장히 느린 secondary storage에 대한 접근 횟수가 현저히 줄어든다.
3. 테이블 Full-Scan시, 모든 노드를 탐색해야하는 B-tree에 비해, B+tree는 리프노드에서 선형 탐색만으로 탐색이 가능하다.

 

 

 

참고: https://zorba91.tistory.com/293

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

참고: https://github.com/wjdansrl7/2024_CS_STUDY/blob/master/DB/B-tree%2C%20B%2Btree.md

2024_CS_STUDY/DB/B-tree, B+tree.md at master · wjdansrl7/2024_CS_STUDY