[TIL] 2025.03.05 B트리

오늘의 키워드

트리구조

MySQL의 DB engine인 InnoDB는 B+tree로 이루어져 있다고 한다.

B+tree는 B-tree의 확장된 개념인데 차이점을 알아보자.

B-tree

일반적인 균형 트리

데이터베이스 및 파일 시스템에서 검색을 빠르게 수행하기 위해 사용된다.

'균형 트리'란?
루트로부터 리프까지의 거리가 일정한 트리 구조를 뜻함
- 트리 중, 성능이 안정화되어있다.

• 각 노드에는 여러 개의 키(key)와 자식 노드를 가질 수 있음.

장점

• 데이터가 모든 노드에 분산되어 있어 루트나 내부 노드에서 검색이 가능하여 탐색 속도가 빠를 수 있음.
  • 어떤 값에 대해서도 같은 시간에 결과를 얻을 수 있다

단점

• 트리의 균형을 유지하기 위해 삽입과 삭제 시 자동으로 재조정
• 범위 검색이 비효율적임 (리프 노드가 따로 연결되어 있지 않음)

 

B+tree

B-tree에서 발전된 형태, 데이터베이스 인덱스에 최적화된 구조

MySQL의 InnoDB도 B+tree를 사용하여 인덱스를 구성

 

B-tree의 경우, internal 또는 branch 노드에 key와 data를 담을 수 있지만,

B+tree의 경우 브랜치 노드에 key만 담아두고, data는 담지 않는다.

오직 리프 노드에만 key와 data를 저장하고, 리프 노드끼리 Linked list로 연결되어 있다. 

• 모든 데이터를 리프 노드에만 저장하고, 내부 노드(Internal Node)는 인덱스(키(Key))만 저장하고 실제 데이터는 저장하지 않음
• 리프 노드 간 더블 링크드 리스트로 연결되어 있어 순차 접근이 효율적
• 검색은 루트에서 시작하여 리프 노드까지 내려가서 데이터 찾음
• 순차 검색이 용이하며, 범위 검색(range scan)에 최적화됨

장점

• 범위 검색이 빠름 (리프 노드가 연결되어 있어 순차적으로 탐색 가능)
  • 리프 노드 간 연결이 되어 있어 범위 검색, ORDER BY, GROUP BY 연산이 B-tree보다 훨씬 효율적
• 내부 노드가 데이터가 아닌 인덱스만 저장하기 때문에 더 많은 키를 저장할 수 있어 트리의 높이가 낮아짐
  • 트리의 높이가 낮아 검색 시 디스크 접근이 줄어들고, 검색 속도가 향상됨.
  • 내부 노드에는 키만 저장하므로 한 페이지에 더 많은 키를 저장할 수 있어 트리의 깊이가 줄어듦. > 효율적인 저장 공간
• 데이터가 전부 리프 노드에 있어, 검색 성능이 일정하게 유지됨
• MySQL의 클러스터형 인덱스 구조와 잘 맞아떨어짐
  
  • InnoDB는 기본 키(Primary Key)를 클러스터형 인덱스로 사용하여 데이터 자체를 리프 노드에 저장할 수 있음.
  • 이를 통해 PK 기반 검색 시 추가적인 테이블 접근 없이 빠르게 데이터 검색 가능.

단점

• 특정 키 하나만 검색할 때는 B-tree보다 성능이 약간 낮을 수 있음 (항상 리프 노드까지 가야 하기 때문)

 

비교

특징	B-tree	B+tree
데이터 저장 위치	모든 노드(루트,리프,브랜치 노드)	리프 노드만
내부 노드 역할	데이터 + 인덱스	인덱스 전용
범위 검색 성능(풀스캔)	낮음(모든 노드 탐색)	높음 (리프 노드 연결 -> 리프노드에서 선형 탐색)
검색 속도	내부 노드에서 찾으면 빠름	항상 리프 노드까지 탐색해야 함
트리 높이	상대적으로 높을 수 있음	더 낮음 (더 많은 키 저장 가능)
사용처	일부 DB, 파일 시스템	대부분의 DB (MySQL InnoDB 등)
키 중복	없음	있음(리프 노드에 모든 데이터가 있어서)
링크드 리스트	없음	리프 노드끼리 링크드 리스트로 연결

 

참고:

https://zorba91.tistory.com/293