왜 B-Tree 를 데이터베이스 인덱스로 선택하는가?
데이터베이스의 탐색 성능을 좌우하는 인덱스는 데이터 저장, 수정, 삭제에 대한 성능을 희생시켜 조회에 대한 성능을 대폭 상승하는 방식으로 구현되어 있는 것을 볼 수 있다.
기본적으로 인덱스를 생성할 때 가장 빠른 해시 테이블을 사용하면 안 되는가? 에 대한 의문이 발생할 수 있다. 모든 자료구조와 그 어떤 알고리즘을 비교해도 탐색 시간이 가장 빠른 것은 바로 해시 테이블이다 > O(1)의 시간 복잡도. 하지만 우리의 데이터베이스는 등호(=) 뿐 아니라 부등호(<, >)를 사용할 수 있다는 점을 이해해야 한다. 해시 테이블은 값이 정렬되어 있지 않으므로, 특정 기준보다 크거나 작은 값을 찾을 수 없다.
OK. 순차 탐색이 불가능하기에 해시 테이블을 인덱스로 활용할 수 없다는 점을 이해했다. 그렇다면 다른 O(logN) 방식의 자료구조나 알고리즘은 왜 사용하지 못 하는 걸까?
그 중 하나의 RedBlack-Tree 를 예시로 들어보자.
RedBlack-Tree는 각 노드가 하나의 값만 가진 상태에서 좌, 우 자식 노드의 개수 밸런스를 맞추게 된다. 이 과정에서 하나의 노드가 가지는 데이터 개수 차이로 인해 무조건 하나의 노드에 하나의 데이터 요소만을 저장해야 하는 것이 단점으로 작용한다. 물론 O(logN)의 이론적인 시간 계산 방식에서는 B-Tree와 차이가 없지만, 실제 메모리에 접근하는 물리적, 절대적인 시간 개념으로는 배열 접근을 시도하는 B-Tree가 빠를 수밖에 없다. 이 차이는 참조 포인터 접근 의 수 때문에 발생하는 문제이다.
B-Tree는 다음과 같이 생겼으며, 배열처럼 정렬되어 있다. 실제 메모리 상에 차례대로 저장이 되어 있어 같은 노드 공간의 데이터(100, 155, 226 등)들끼리 굳이 자식 노드처럼 참조 포인터 값으로 접근할 필요가 없다. 이는 실제 메모리 디스크에서 바로 다음 인덱스의 접근을 하는 것이다. 여기에 데이터가 존재하지 않을 경우, 참조 포인터에 접근하게 되므로, RedBlack-Tree 보다 접근 횟수가 적어지는 특징을 가지고 있다.
모든 면에서 DB 인덱스 용도로 가장 적합한 자료구조인 B-Tree
- 항상 정렬된 상태로 특정 값보다 크고 작은 부등호 연산에 문제가 없다.
- 참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능하다.
- 데이터 탐색 뿐 아니라, 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도를 가진다.
이번 블로그 글에서는 두 가지 알고리즘의 특징과 차이점을 비교해보고자 한다.
M원 검색 트리(M-way Search Tree)
그 전에 먼저 M원 검색 트리부터 이해하고 넘어가고자 한다.
M원 트리는 한 노드 안에 최대 m-1개의 요소와 m개의 자식을 가질 수 있는 구조의 트리이다. 각 노드는 다음과 같은 특징을 가지고 있다.
-
각 노드는
0 <= 서브트리개수 <= m만큼 서브 트리를 가질 수 있다. -
K개의 자식 노드를 가지는 노드는
K-1개의 요소를 가질 수 있다. (K≤M) -
각 노드 안에 있는 키는 오름차순으로 정렬되어 있다.
-
i번째 Key < i 번째 서브 트리 내의 모든 키 값 <i+1번째 Key -
모든 서브 트리는 m-원 검색 트리이다.
B-Tree(Balanced Tree)
m-원 검색 트리로 높이(Depth)를 대폭 줄였지만, Key 값들의 균형이 맞지 않는다는 문제가 존재한다. B-Tree 에서는 이 점을 보완하고 데이터가 정렬된 상태로 유지되어 있을 수 있도록 한다.
B-Tree는 균형 트리로 루트로부터 리프까지의 거리가 일정한 트리 구조를 가진다. 균형을 유지하는 경우, 어떤 데이터를 검색할 때 동일하게 빠른 속도로 데이터를 찾을 수 있다. 그러나 트리의 노드가 수정되어야 하는 경우, 재정렬의 필요성 때문에 수정 시 단점이 존재한다.
3차 B-Tree
3차 B-Tree의 예시를 보며, 삽입과 삭제에 대한 예시는 그림으로 대체하도록 하겠다.
B+Tree
B-Tree 와 비슷한 구조의 트리이지만, 가장 큰 차이점은 리프 노드를 제외하고 실제 데이터를 보관하고 있지 않기 때문에 하나의 블록에 더 많은 Key 값을 담아 둘 수 있다는 장점이 있다. 이는 곧, 생성되는 노드의 수를 줄여 트리의 높이(Depth)가 낮아짐을 의미하는데, 풀 스캔시 B+Tree는 리프 노드에 데이터가 모두 존재하기 때문에 한번의 선형 탐색만 하면 되기 때문에 B-Tree 보다 빠르다는 장점이 있다. 같은 레벨의 노드에서는 Double Linked List 를 사용하고, 자식 노드는 Single Linked List를 사용한다.
차이점을 정리하면 다음과 같다.
- 인덱스 세트(내부 노드)에 있는 키 값
리프 노드에 있는 키 값을 찾아가는 경로만 제공하며, 인덱스 세트에 있는 키 값은 대부분 순차 세트에 다시 나타남 - 인덱스 세트의 노드와 순차 세트의 노드는 그 내부 구조가 서로 다름
인덱스 세트에 있는 노드 : 키 값만 저장된다.
리프 노드 : 키 값과 포인터를 함께 저장한다. - 순차 세트의 모든 노드가 순차적으로 서로 연결된 연결 리스트 > 순차 탐색 및 범위 검색에서 효율적
B-Tree vs B+Tree
| 특성 | B-Tree | B+Tree |
|---|---|---|
| 내부 노드 | 키와 데이터를 가짐 | 키만 가짐 |
| 리프 노드 | 데이터와 포인터를 가짐 | 데이터만 가짐 |
| 연결성 | 리프 노드 간 연결 없음 | 리프 노드가 연결 리스트 형태로 연결됨 |
| 범위 쿼리 성능 | 효율적이지 않음(중위 순회) | 매우 효율적 (리프 노드 순차 탐색) |
| 사용 사례 | 전반적인 검색과 삽입/삭제 성능이 중요할 때 | 대용량 데이터에서의 범위 검색이 중요할 때 |
결론
B-Tree와 B+Tree는 데이터베이스와 파일 시스템에서 대용량 데이터의 효율적인 검색과 정렬을 위해 설계되는 균형 트리이다. 두 구조 모두 노드 간 균형을 유지하여 탐색 시간을 줄이고, 빠른 삽입, 삭제, 검색이 가능하도록 설계하는 알고리즘이다.
- B-Tree는 삽입과 삭제가 자주 발생하는 환경에서 효율적
- B+Tree는 범위 검색이 빈번한 데이터베이스와 파일 시스템에서 효율적
각 트리 구조는 사용 목적에 따라 선택되며, 그 동작 원리를 이해하는 것이 중요할 것으로 예상된다.
