[MySQL] B+tree

 

1. B+tree 란?

 

  - B+tree는 데이터베이스와 파일 시스템에서 널리 사용되는 균형 잡힌 트리 자료 구조

 

  - B+트리는 B-트리(B-tree)를 개선한 것( 인접한 자식 노드 끼리 링크드 리스트로 연결 )

 

  - 큰 데이터 세트를 효율적으로 관리하는 데 유용

 

 

2. B+tree 특징

 

  - 모든 실제 데이터는 리프 노드에만 저장, 내부 노드는 경로 탐색을 위한 인덱스 키 저장

 

  - 리프 노드는 서로 링크드 리스트 형태로 연결( 범위 검색과 순차 접근이 효율적 )

 

  - 트리는 삽입 및 삭제 시 자동으로 균형을 유지하여 검색, 삽입, 삭제의 시간 복잡도를 O(log n)으로 보장

 

 

3. B+tree 작동 방식

 

  - 검색 : 루트 노드에서 시작하여 리프 노드까지 내려감, 내부 노드에서 키를 비교하여 적절한 자식 노드를 선택

 

  - 삽입 : 루트 노드에서 시작하여 적절한 리프 노드를 찾아 내려감, 리프 노드에 공간이 있으면 새 키-값 쌍을 추가하고 공간이 부족하면 리프 노드를 분할 후 부모 노드에 새 인덱스 키를 추가

 

  - 삭제 : 루트 노드에서 시작하여 리프 노드까지 내려감, 리프 노드에서 키-값 쌍을 삭제하고 노드의 키 수가 최소값 미만이면 인접한 노드와 병합하거나 키를 재분배

 

 

4. B+tree 특징

 

  - 리프 노드가 연결 리스트 형태로 연결되어 있어 순차 접근과 범위 검색이 빠름

 

  - 각 노드가 많은 자식을 가질 수 있어 트리의 높이가 낮아짐( 검색, 삽입, 삭제의 성능 향상 )

 

  - 트리는 항상 균형을 유지하므로 성능이 일관적임

 

  - 한 노드에 많은 키를 저장하므로 디스크 접근 횟수가 줄어듬