포스트

DB 인덱스가 B+Tree 계열 자료구조를 사용하는 이유

DB 인덱스가 B+Tree 계열 자료구조를 사용하는 이유

들어가며

데이터베이스에서 인덱스를 추가하면 조회 성능이 높아진다는 것은 알고 있었습니다. 하지만 인덱스가 내부에서 어떤 자료구조를 사용하는지, 그리고 왜 그 자료구조를 사용하는지에 대해서는 깊게 생각해보지 않았습니다.

학교 후배들에게 멘토링을 진행해주며 B-Tree 와 B+Tree 에 대해서 복습하게 되었고, 데이터베이스는 어떤 식으로 이 자료구조를 사용하는지 궁금해졌습니다.

이를 이해하기 위해서 단순히 시간 복잡도만 비교하지 않고 데이터베이스가 데이터를 저장하고 읽는 방식과 Disk I/O 비용까지 함께 살펴볼 필요가 있었습니다.

이번 글에서는 B-Tree 와 B+Tree 의 구조를 살펴보고 이러한 구조가 데이터베이스 인덱스에 적합한 이유를 정리해보려고 합니다.

1. Binary Search Tree 로는 부족한가?

BST의 문제점은 한쪽으로만 가지가 뻗어져 나가면 탐색의 시간 복잡도가 최악의 경우 O(N) 이 될 수 있다는 것입니다.
한쪽으로만 자식이 이어져 높이가 N이 된 편향 이진 탐색 트리
물론 AVL Tree 같은 방법을 사용하면 이러한 문제를 해결할 수 있습니다. 트리의 균형을 유지하기 때문에 탐색, 삽입, 삭제를 O(log N) 으로 수행할 수 있습니다.

균형 잡힌 BST 역시 O(log N) 의 탐색이 가능한데 데이터베이스는 왜 B-Tree 계열의 자료구조를 사용할까요? 이 이유를 이해하기 위해서는 시간 복잡도뿐만 아니라 데이터를 읽을 때 발생하는 Disk I/O 비용을 함께 살펴봐야 했습니다.

2. DB는 트리의 높이가 중요하다

데이터베이스에서는 데이터를 Disk 에 저장합니다. 여러분도 아시겠지만 메모리에서 데이터를 읽는 것과 비교하면 Disk 에서 데이터를 읽는 것은 훨씬 큰 비용이 발생합니다. 즉, 비교 연산을 몇 번 수행하는지보다는 데이터를 찾기 위해서 Disk 에 몇 번 접근하는지가 중요했습니다.

BST의 경우는 2개의 자식만 가질 수 있기에 데이터 개수가 많아질수록 트리의 높이가 계속 증가합니다. 반면에 B-Tree 와 같은 Multiway-Tree 는 하나의 노드가 여러 개의 Key 와 자식을 가질 수 있기 때문에 훨씬 낮은 높이의 트리를 만들 수 있습니다.

트리의 높이가 낮다는 것은 원하는 데이터를 찾기 위해 방문해야 하는 노드의 개수가 줄어든다는 의미이고, Disk I/O 횟수를 줄일 수 있다는 의미였습니다.

이러한 이유로 하나의 노드가 많은 자식을 가질 수 있는 B-Tree 계열의 자료구조가 데이터베이스 인덱스에 적합했습니다.

3. B+Tree 와 B-Tree 는 무엇이 다를까?

이 두 Tree는 전체적인 구조는 비슷하지만 데이터를 저장하는 위치와 Leaf 노드의 연결에서 중요한 차이가 있습니다.

B-Tree

내부 노드와 Leaf 노드 모두에 실제 데이터 또는 데이터를 가리키는 정보를 저장합니다. 원하는 Key를 내부 노드에서 발견한다면 바로 탐색을 종료할 수 있습니다.

B+Tree

반면에 B+Tree 에서는 내부 노드를 탐색을 위한 Key만 저장하는 공간으로 사용하고 실제 데이터는 Leaf 노드에 저장합니다. 내부 노드는 데이터가 어느 방향에 있는지 알려주는 이정표 역할이었습니다.
내부 노드에는 키만 두고 Leaf 노드들을 순서대로 연결한 B+Tree

B-Tree 에서는 Leaf 노드가 독립적이었지만 B+Tree에서는 Leaf 노드를 Linked List 처럼 순서대로 연결했습니다. 이러한 구조 때문에 B+Tree 에서는 특정 범위의 데이터를 연속해서 읽는 작업도 효율적으로 수행할 수 있었습니다.

4. B+Tree 와 SQL 문법

예를 들어서 다음과 같은 쿼리를 생각해낼 수 있습니다.

1
2
SELECT * FROM member
WHERE age BETWEEN 20 AND 30;

나이가 20부터 30까지 연속된 데이터를 찾아야 할 때 B+Tree 에서는 처음 20을 찾은 이후 Leaf 노드를 순서대로 이동하면서 데이터를 읽으면 됩니다.

범위 탐색에 매우 유리하다는 것을 알 수 있습니다.

5. 그래서 DB 인덱스에 B+Tree 가 적합하다!

B+Tree 는 데이터베이스가 원하는 특성을 대부분 가지고 있습니다.

  1. 트리의 높이가 낮다
    한 노드가 많은 자식을 가질 수 있기 때문에 Disk I/O 횟수를 줄일 수 있습니다.
  2. 항상 균형을 유지한다
    최악의 경우에도 일정한 탐색 성능을 유지할 수 있습니다.
  3. 범위 검색에 강하다
    Leaf 노드가 연결되어 있기 때문에 연속된 데이터를 빠르게 탐색할 수 있습니다.
  4. 정렬된 상태를 유지한다.

6. 실제 데이터베이스에서는?

중요한 점은 모든 DB가 B+Tree 를 그대로 구현하는 것은 아닙니다.
대부분의 관계형 데이터베이스는 B-Tree/B+Tree 계열의 자료구조를 기반으로 정렬된 인덱스를 구현한다고 이해하는 게 좋습니다.


마치며

데이터베이스에서는 시간 복잡도만 중요한 것이 아니라 Disk I/O 를 줄이는 것이 중요하다는 점과 B+Tree 의 Leaf 노드 연결 구조가 범위 탐색에 유리하다는 점을 알게 되었습니다.

이제는 단순히 인덱스를 사용하는 것에서 끝나지 않고, 적절한 인덱스를 설계하는 등 실제 데이터베이스 성능 튜닝에도 도전해보고 싶다는 생각이 들었습니다.

앞으로는 쿼리가 어떻게 실행되는지, 인덱스가 언제 사용되고 언제 오히려 비효율적일 수 있는지까지 공부하면서 데이터베이스를 조금 더 깊게 이해해보려고 합니다.

이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.