B-Tree로 설계하는 디스크 기반 인덱스

디스크 페이지를 기준으로 높이를 낮추는 트리

B-Tree는 대용량 데이터를 인덱싱하기 위한 균형 트리다. 정렬된 키를 기준으로 탐색·삽입·삭제를 수행하며, 모든 리프 노드는 같은 레벨에 놓인다. 따라서 특정 방향으로 트리가 길어지는 현상을 막고 탐색 경로 길이를 균등하게 유지할 수 있다.

각 노드의 키는 정렬 상태를 유지한다. 중위 순회(in-order traversal)를 수행하면 정렬된 값을 얻을 수 있으며, 연산은 항상 루트 노드에서 시작한다. 분할이나 병합이 일어나면 루트 자체가 바뀔 수도 있다.

최소 차수 t(minimum degree)를 기준으로 보면, 루트를 제외한 노드는 t−1개에서 2t−1개 사이의 키를 유지한다. 2t−1개의 키로 가득 찬 노드에 삽입이 들어오면 분할이 발생한다. 이 규칙은 각 노드가 최소 절반 이상 채워지도록 한다.

노드 하나에 많은 분기를 담는 이유

B-Tree의 높이는 페이지당 포인터 수인 브랜치 팩터에 따라 O(log_m N)으로 유지된다. m은 디스크 페이지 크기와 키 크기에 따라 결정된다. 수백수천 브랜치를 구성할 수 있으면 대규모 N에서도 높이는 35 레벨 수준으로 작아진다.

노드는 정렬된 키 배열과 자식 포인터 배열로 구성된다. 키 사이의 구간은 각각 하위 서브트리에 대응하며, 현재 노드에서 이진 탐색이나 선형 탐색으로 위치를 찾은 뒤 해당 자식으로 내려간다.

이 구조는 노드를 디스크 페이지 크기에 맞춰 배치해 I/O를 줄이는 데 초점이 있다. 내부 노드에도 값이 존재하므로, 순차 범위 스캔은 B+Tree보다 비효율적일 수 있다.

삽입과 삭제에서는 구조적 수정(SMO)이 필요하다. 삽입 시 오버플로가 나면 노드를 분할하고 중간 키를 상위 노드로 올린다. 삭제 중 언더플로가 발생하면 형제 노드에서 키를 재분배하거나 병합하며, 루트가 축소될 수도 있다.

키를 찾고 넣고 지우는 과정

탐색은 루트에서 시작해 현재 노드의 키 위치를 찾고, 해당 구간의 자식 포인터를 따라 내려가는 방식이다. 리프에 도달하면 키의 존재 여부를 판단한다. 평균적인 노드 접근 비용은 O(log_m N)이며, 노드 내부 탐색은 O(log k) 또는 O(k)이고 k는 노드의 키 수다.

삽입은 하강 전에 가득 찬 노드를 처리하는 방식으로 구성할 수 있다. 루트가 가득 찼다면 먼저 분할하고, 하강 중 선택한 자식이 가득 찼다면 즉시 분할한 뒤 적절한 자식을 다시 골라 내려간다. 리프에서 키를 넣은 뒤에도 노드 내부의 정렬은 유지해야 한다. 중복 키는 무시, 카운트 증가, 덮어쓰기 등 정책을 미리 정해야 한다.

삭제 대상이 내부 노드에 있으면 전임자 또는 후임자 키로 바꾼 뒤 리프에서 삭제한다. 이후 언더플로가 생기면 형제에서 키를 빌리거나 병합한다. 루트가 비면 높이는 1 감소하며, 공집합 루트도 정리 대상이다.

⤢✕

중복 키를 허용하지 않는 구조라면 탐색 성공 시 삽입을 중단해야 한다. 키 비교 규칙도 컬레이션과 바이너리 비교를 포함해 일관돼야 한다. 분할이나 병합 도중 부분 실패가 발생할 수 있으므로 원자성도 필요하다. 데이터베이스에서는 래치와 로그 기반 트랜잭션으로 이를 처리한다.

동시 접근에서는 상위에서 하위로 잠그는 탐색 래치 커플링(latch coupling)을 적용할 수 있다. 분할·병합에는 구조 수정 래치(SMO)를 별도로 적용한다. 복구는 Write-Ahead Logging을 이용해 원자성과 내구성을 보장하며, 순서는 로그 기록 후 페이지 쓰기다.

인덱스와 메타데이터에서의 사용

데이터베이스 인덱스는 B-Tree 원리를 대표적으로 사용하는 영역이다. OLTP 인덱스에서는 B+Tree가 일반적이지만, 등치 질의와 범위 질의를 지원하는 B-Tree의 균형·분할 원리는 동일하게 적용된다. 세컨더리 인덱스, 조인 키 가속, UNIQUE 제약 구현에도 활용된다.

파일시스템과 스토리지에서는 디렉터리 엔트리와 메타데이터 인덱싱에 적합하다. 대량의 파일과 블록을 관리하면서 저널링과 결합하면 크래시 복구도 수월해진다.

키-값 저장소나 캐시의 온디스크 인덱스도 페이지 단위 데이터 레이아웃과 잘 맞는다. SSD에서 읽기 효율을 높이고, 메모리가 부족한 환경에서는 외부 메모리 접근을 최적화하는 데 쓸 수 있다.

운영에서 확인할 특성

탐색·삽입·삭제는 평균과 최악 모두 O(log_m N)이다. 브랜치 팩터 m이 커질수록 필요한 I/O 수는 줄어든다. m=256, N=10^9 레코드를 가정하면 높이는 ≈ log_256(10^9) ≈ 3.5이며, 4단계 내 접근이 가능하다.

노드는 최소 50% 이상 점유하므로 공간 효율성을 확보할 수 있고, 분할과 병합은 균형을 자동으로 유지한다. 페이지 크기를 조정해 m도 조절할 수 있다. 모든 리프가 같은 레벨에 있으므로 작업 이후에도 탐색 경로 길이가 균등하며, 구조적 수정은 부분 페이지 변경에 국한된다.

지표	내용
성능	탐색/삽입/삭제 O(log_m N), 노드 내부 탐색 O(log k) 또는 O(k)
확장성	브랜치 팩터에 따라 높이 3~5 레벨로 수십억 행 처리 가능
일관성	모든 리프 동일 레벨, 최소 50% 점유 규칙으로 균형 유지
안정성	분할/재분배/병합으로 언더/오버플로 처리, 루트 축소 지원
운영 편의	디스크 페이지 정합 최적, 대범위 순차 스캔은 비권장(B+Tree 선호)

B-Tree는 균형 유지와 낮은 높이, 디스크 친화적 레이아웃을 결합해 대규모 데이터에서 균등한 탐색 지연을 제공한다. 다만 분할·병합에 따른 구조 유지 비용이 있으며, 대범위 순차 스캔이 주된 업무라면 B+Tree를 검토할 필요가 있다.