[20250422] B-Tree 와 B+Tree 란?

• B트리
  • 내부 노드와 리프 노드 모두에 데이터를 저장
  • 즉, 트리의 모든 노드가 **키(key)**와 그에 해당하는 **데이터(value)**를 포함할 수 있음.
  • 예: 검색 중 내부 노드에서 원하는 키를 찾으면, 그 자리에서 데이터를 바로 반환할 수 있음.
• B+트리
  • 리프노드에만 데이터 저장
  • 내부 노드는 키와 자식 노드에 대한 포인터만 포함하며, 데이터는 저장하지 않음.
  • 예: 검색 시 반드시 리프 노드까지 내려가야 데이터를 찾을 수 있음.

저장위치가 바뀌었기 때문에 검색 방식도 바뀐다.

• B트리
  • 검색 시 내부 노드에서 원하는 키를 찾으면 바로 데이터를 반환
  • 장점: 경우에 따라 리프 노드까지 가지 않아도 데이터를 찾을 수 있어, 특정 상황에서 더 빠를 수 있다.
  • 예: 루트나 중간 노드에서 키를 발견하면 즉시 검색 완료.
• B+트리
  • 모든 데이터가 리프 노드에 있으므로, 검색은 항상 리프 노드까지 진행.
  • 내부 노드는 검색 경로를 안내하는 인덱스 역할만 수행
  • 예: 내부 노드에 키가 있어도, 실제 데이터는 리프 노드에 있으므로 끝까지 탐색해야함.

이 차이점(리프노드구조)이 B+를 특별하게 만들 수 있게 한다.

• B트리
  • 리프 노드가 서로 연결되어 있지 않음.
  • 순차적으로 데이터를 읽으려면 트리 전체를 탐색해야함. 순차 접근 비효율
• B+트리
  • 모든 리프 노드가 링크드 리스트처럼 서로 연결되어 있다.
  • 리프 노드에 도달하면 연결된 노드를 따라 순서대로 데이터를 읽을 수 있어, 순차 접근이 매우 효율적.
  • 예: 데이터가 순서대로 정렬되어 있어, 다음 노드로 바로 이동 가능.

• B트리
  • 범위 검색(예: 10~20 사이의 데이터 조회) 시, 데이터가 내부 노드와 리프 노드에 흩어져 있어 비효율적.
  • 내부 노드와 리프 노드를 모두 방문해야 할 수 있으며, 순차적으로 데이터를 모으려면 트리를 여러 번 탐색해야함.
  • 결론: 대량 데이터 순차 읽기에서 성능 저하.
• B+트리
  • 모든 데이터가 리프 노드에 순서대로 저장되어 있고, 리프 노드들이 연결되어 있어 범위 검색이 매우 효율적
  • 리프 노드에 도달한 후, 연결된 노드를 따라가며 원하는 범위의 데이터를 빠르게 수집할 수 있음.
  • 예: 데이터베이스의 "SELECT * FROM table WHERE id BETWEEN 10 AND 20" 같은 쿼리에서 우수한 성능.

• B트리
  • 내부 노드에도 데이터를 저장하므로, 한 노드에 저장할 수 있는 키의 수가 상대적으로 적음
  • 트리의 높이가 더 높아질 수 있으며, 검색 시 더 많은 디스크 I/O가 발생할 가능성이 있음을
• B+트리
  • 내부 노드는 키만 저장하므로, 한 노드에 더 많은 키를 포함할 수 있음. (내부노드에 들어가는 값이 많아짐)
  • 트리가 높이가 낮아짐. 검색 시 디스크 I/O 감소.
  • 대용량 데이터에서 검색 성능이 더 우수.

• B트리
  • 주로 파일 시스템에서 사용.
  • 예: 디렉토리 구조에서 각 노드가 파일이나 서브디렉토리 정보를 저장하며, 내부 노드에도 데이터가 필요.
  • 일부 데이터베이스에서도 사용되지만, 범위 검색이 적은 경우에 적합.
• B+트리
  • 데이터베이스 인덱스에서 널리 사용.
  • 예: MySQL, Oracle, SQL Server 등 대부분의 관계형 데이터베이스 관리 시스템(RDBMS)에서 인덱스로 활용.
  • 범위 검색과 순차 접근이 중요한 작업에 최적화.