B-트리는 왜 디스크 인덱스에 어울릴까? 노드와 범위 조회

데이터베이스 인덱스가 찾는 것은 메모리 안의 값 하나가 아니라 저장장치에 있는 많은 페이지다. 이때 한 번 읽을 때마다 다음 위치를 하나만 알 수 있는 트리보다, 한 페이지 안에서 여러 갈림길을 판단할 수 있는 구조가 유리하다. B-트리는 이 조건에 맞춰 한 노드에 여러 키와 자식을 담는 정렬 트리다.

해시 테이블이 “이 키와 같은 값은 어디 있나”에 강하다면, B-트리는 “이 값보다 작은 것과 큰 것은 어디 있나”, “이 구간의 값은 무엇인가”를 빠르게 찾기 위해 만든다.

노드 하나는 저장장치 페이지 하나처럼 읽힌다

작은 B-트리 노드가 10과 30을 가진다고 하자. 26을 찾을 때는 10보다 크고 30보다 작으므로 가운데 자식으로 내려간다.

       [10 | 30]
       /    |    \
   <10   10~30   >30

실제 데이터베이스에서는 이 노드 하나를 디스크나 SSD에서 읽는 페이지에 맞춘다. 한 번 읽은 노드에서 많은 키를 비교하고 다음 자식을 고르면, 루트에서 리프까지 가는 단계가 줄어든다. B-트리가 이진 트리처럼 자식을 둘만 두지 않는 이유다.

삽입은 빈 자리에 넣는 일보다 정렬 규칙을 지키는 일이다

한 노드에 키 두 개까지만 넣을 수 있다고 단순화해 보자. 10, 20이 든 노드에 30을 넣으면 세 키가 되어 넘친다.

[10 | 20 | 30]
      ↓ 분할
       [20]
      /    \
   [10]  [30]

가운데 20은 부모로 올라가고, 작은 키와 큰 키는 아래 두 노드에 남는다. 이 분할 덕분에 어느 노드도 지나치게 커지지 않고, 루트에서 리프까지의 거리가 크게 한쪽으로 쏠리지 않는다.

40을 넣을 때는 20보다 큰 쪽으로 내려가 [30 | 40]에 넣는다. 중요한 것은 키가 어떤 노드에 있느냐가 아니라, 모든 노드에서 왼쪽 자식은 더 작은 범위, 오른쪽 자식은 더 큰 범위라는 약속이 계속 유지되는 것이다.

범위 조회는 정렬된 순서를 이용한다

20 이상 40 이하를 찾을 때는 먼저 20이 시작되는 위치를 찾는다. 그 뒤 리프의 정렬된 키를 오른쪽으로 읽다가 40을 넘으면 멈춘다.

시작 키 20 찾기
  → 20, 30, 40을 순서대로 읽음
  → 다음 키가 40보다 크면 종료

해시 테이블에서는 20부터 40까지라는 순서 자체가 없다. 원하는 키와 같은 버킷을 찾는 데는 좋지만, 범위 전체를 얻으려면 많은 키를 확인해야 할 수 있다. 정렬과 범위 조회가 필요할 때 B-트리 인덱스를 쓰는 이유다.

인덱스는 읽기를 빠르게 하지만 쓰기 경로도 늘린다

인덱스가 있으면 원하는 행을 찾는 길이 생긴다. 하지만 행을 새로 넣거나 인덱스 키를 바꾸면, B-트리도 새 키를 넣고 필요하면 분할해야 한다. 인덱스를 여러 개 만들수록 한 번의 쓰기가 여러 트리를 갱신하게 된다.

또 인덱스로 키를 찾았더라도 필요한 열이 인덱스에 없다면 본문 데이터를 다시 읽어야 한다. 그래서 “인덱스가 있다”만으로 빠르다고 말할 수 없다. 어떤 조건과 정렬, 어떤 결과 범위를 자주 읽는지를 기준으로 인덱스를 정해야 한다.

삭제 뒤에도 트리 모양을 유지해야 한다

키를 지우면 어떤 노드는 너무 비어 있을 수 있다. 이때 이웃 노드에서 키를 빌리거나 둘을 합쳐야 정렬과 노드 크기 규칙이 유지된다. 삽입의 분할과 삭제의 병합은 모두 같은 목적을 가진다. 어느 리프까지 내려가도 트리 높이와 키 범위가 크게 어긋나지 않게 하는 것이다.

이해 확인 질문과 답변

B-트리는 왜 한 노드에 키를 여러 개 둘까?

저장장치에서 노드를 읽는 비용이 크기 때문이다. 한 번 읽은 노드에서 많은 갈림길을 판단하면 트리 높이가 낮아지고, 큰 데이터에서도 필요한 페이지 읽기를 줄일 수 있다.

해시 테이블 대신 B-트리를 항상 쓰면 안 될까?

동등 조회만 중요하면 해시 테이블이 더 단순할 수 있다. B-트리는 키 순서와 범위 조회를 얻는 대신 분할·병합 같은 유지 규칙과 쓰기 비용이 생긴다.

범위 조회 결과가 이미 정렬돼 있는 이유는 무엇일까?

B-트리의 키와 리프가 순서대로 배치돼 있기 때문이다. 시작 위치를 찾은 뒤 옆 순서로 읽으면 범위 안의 값을 정렬된 순서로 얻을 수 있다.

인덱스를 많이 만들면 모든 조회가 빨라질까?

아니다. 인덱스가 맞지 않는 조건에는 쓰이지 않을 수 있고, 인덱스가 많을수록 삽입·수정·삭제 때 갱신할 구조가 늘어난다. 실제 조회 질문을 기준으로 필요한 인덱스를 고르는 편이 맞다.

AI에게 이렇게 요청할 수 있다

키 두 개만 담는 작은 B-트리에 10, 20, 30, 40을 삽입하는 과정을 설명해 줘. 노드 분할, 트리 높이, 20부터 40까지의 범위 조회, 인덱스가 쓰기 경로에 주는 영향까지 보여 줘.

B-트리를 이해했다면 인덱스를 볼 때 “키를 빨리 찾는다”에서 끝나지 않고, 몇 번의 페이지 읽기로 범위를 찾으며 그 길을 유지하기 위해 어떤 쓰기를 하는지까지 생각할 수 있다.