Database

[Indexing] B-트리 (B-Tree) 탐색

Atriel 2025. 4. 8. 15:05

B-트리 란?

B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.

 

라는데.. 인덱싱이니 탐색 효율을 늘리는 방법인건 알겠는데

코딩테스트를 준비하면서 익숙한게 아니라면 어색할 수도 있다.

위의 정의는 보고 감만 잡아보고 그림으로 이해 해보자

 

 

https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC

 

이런식의 트리 구조 형태로 B-tree가 있다고 해보자

총 3개의 계층 구조로 나눠져 있으니 3차 B-tree라고 볼수있다.

 

눈에 보이는 직관적인 그대로 값을 크기기준으로 나눠서 자식노드를 찾아가는 방법으로

조회하는 데이터의 수를 줄인것이다.

 

예를들어 2라는 값을 찾고자 하면

 

맨 처음 루트노드에서 10, 20이란 2가지의 기준으로 범위(중간노드)를 3가지로 나눈다

10 이하,  10과 20사이, 20이상

 

그럼 찾으려는 값 2는 10이하이니 왼쪽 중간노드를 자식포인터를 향해 들어가게되고

2층 중간노드에서는 5를기준으로 다시 5이하, 5이상 두가지 기준으로 나누게되고

찾으려는 값은 2이니 왼쪽 리프노드 (자식노드)를 타서 주어진 범위만 조회하게 된다.

 

특정 값을 조회할 때, 해당 값이 존재할 가능성이 있는 하위 트리 경로만 따라 내려가며 탐색하고, 나머지 범위는 아예 조회하지 않는다. 

이게 B-트리가 효율적인 이유이자 쓰는 이유다.

 

위의 그림은 루트로드에서 3분할, 왼쪽 중간노드에서 2분할이 됬지만

만약 구간(예를들어 1차노드에 0이상, 10이하의 범위) 범위에 담아야할 데이터가 정해진 일정 갯수보다 더 많다면
분할 갯수를 늘려서 효율적인 인덱싱이 될 수 있게 범위를 더 세분화 하게 된다.
(이 부분은 굳이 개발자가 명시적으로 할 수는 있지만, 보통 라이브러리가 효율적인 인덱싱을 할 수 있게 알아서 조절해줌)


일반적으로는 개발자가 b-tree 구조를 사용할때 명시하는 값은
최소 차수(3차 트리구조로 할꺼냐.. 4차로 할꺼냐 등등)와 키 값의 비교 로직(Comparable인터페이스를 구현하는거라던지..)등이 있다. 


여기서 드는 궁금점

그냥 마구마구 작은 범위로 분할해서 트리 갯수를 막늘리면 속도가 빨라져서 좋은게 아닌가~

분할을 더 촘촘하게해서 트리갯수를 늘리면 트리의 높이(차수)가 감소해서 검색은 더 빨라질수 있지만

분기갯수를 무작정 늘리다 보면

  • 노드 크기 증가: 분기 계수가 커지면 각 노드가 저장해야 하는 키와 자식 포인터의 수가 많아져 노드의 크기가 커집니다.
  • 노드 접근 비용 증가: 노드의 크기가 커지면 디스크에서 하나의 노드를 읽어오는 데 더 많은 시간이 소요될 수 있습니다. 또한, 메모리에 로드된 노드 내에서 원하는 키 값을 찾는 데 (선형 탐색 또는 이진 탐색) 시간이 더 걸릴 수 있습니다.
  • 메모리 사용량 증가: 특히 트리의 중간 노드들이 커지면 메모리 사용량이 증가할 수 있습니다.
  • 삽입 및 삭제 비용 증가: 노드가 꽉 찼을 때 분할하거나, 노드가 너무 비었을 때 병합하는 연산의 비용이 증가할 수 있습니다. 분할 또는 병합 시 더 많은 데이터를 이동해야 할 수 있습니다.

이런 단점들이 있다고 한다.

따라서 B-트리의 성능을 최적화하기 위해서는

하드웨어 특성 (디스크 블록 크기, 메모리 페이지 크기 등), 데이터의 크기, 그리고 예상되는 연산 (검색, 삽입, 삭제 빈도) 등을 종합적으로 고려하여 적절한 분기 계수를 선택하는 것이 중요하다.

그래서 이걸 어디에서 쓰느냐~

물론 목적에 따라서 Java나 Python 등에서도 라이브러리로 가져와서 쓸수는 있겠지만

보통은 RDB에서 CRUD 속도를 향상시키기 위해서 사용한다

내가 보통 하는 웹 프로젝트에서는
MySQL 단에서 직접 인덱스를 만들거나
Spring에서 JPA를 통해 만들수 있다 (JPA로 만들어도 실제로는 SQL엔진에서 작동하는것)

 

ALTER TABLE 테이블이름 ADD INDEX 테이블 인덱스이름 (column이름);

MySQL에서 사용하는 가장 일반적인 인덱스 구조가 B-Tree이다.

DDL로 간단히 만들수 있다

 

또는 Spring JPA의 @Index 어노테이션을 이용해서 만들수도 있다

@Entity
@Table(name = "your_table")
@Getter
@Setter
public class YourEntity {
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    @Column(name = "your_column")
    @org.hibernate.annotations.Index(name = "idx_your_column") // Hibernate 관련 어노테이션
    private String yourColumn;

    // ...
}

 

만약 데이터를 추가, 삭제하는과정에서
key갯수가 너무 많거나 적다면, 즉 해당 차수에 데이터가 너무많거나 아예없어진다면
노드를 분할하거나 삭제후 재구성을 하게된다
자세한건 그림을 보면서 참고하길 (참고글: https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC)

 

 

 

 

 

 

저작자표시 비영리 (새창열림)