[B+Tree/BTree/BST/Hash Table] 인덱스에서 B+Tree를 사용하는 이유

Computer Science/Data Structure

[B+Tree/BTree/BST/Hash Table] 인덱스에서 B+Tree를 사용하는 이유

빵빵0 2024. 9. 17. 16:10

DB 설계에서 가장 중요한 인덱스에 대해서 아는게 너무 없는 것 같아 개인적으로 공부한 내용들이다.

데이터 구조

인덱스는 왜 B+Tree를 사용하고 있을까? 이 질문에 대한 해답을 찾기에 앞서, 탐색에 용이한 데이터 구조들과 특징들에 대해 살펴보자.

Binary Search Tree(BST)

이진 탐색 트리(Binary Search Tree, BST)는 이진 탐색과 연결 리스트(Linked List)의 장점을 결합한 자료구조이다.

이진탐색
장점: 탐색에 소요되는 시간복잡도가 O(log N)으로 빠르다.

연결 리스트
장점: 자료 입력, 삭제에 필요한 시간 복잡도가 O(1). (하지만 맨 앞 또는 맨 뒤의 데이터에 대해서만 시간 복잡도가 O(1)이고 특정 노드 다음에 삽입, 삭제가 이루어지는 경우에는 O(n+1) 만큼의 시간이 소요됨)
단점: 탐색하는데 O(n)의 시간 복잡도를 가진다.

트리의 각 노드는 최대 두개의 자식 노드를 가질 수 있다. 또한, 왼쪽 자식 노드는 부모 노드 보다 작은 값을 가지며, 오른쪽 자식 노드는 부모 노드보다 큰 값을 갖는 구조를 유지한다. 이런 정렬을 통해 효율적인 검색과 삽입이 가능하다.

단점

불균형

위 그림과 같이 균형이 잡힌 이진 탐색 트리의 경우, 검색 시간 복잡도는 O(log N)이지만, 아래와 같이 균형이 잡히지 않은 이진 탐색의 경우에는 시간 복잡도가 O(N)까지 수렴하게 되면서 이진 탐색의 장점을 가질 수 없게 된다. (거의 선형 검색과 다를 바 없는 성능)

불균형 트리는 삽입하는 데이터 순서에 따라 얼마든지 발생될 수 있으며, 예를 들어 삽입할 데이터가 이미 정렬된 상태일 경우 불균형이 발생 가능하다.

DB에 적합하지 않은 구조

또, BST는 데이터베이스와 같이 디스크에 데이터를 저장하는 용도로 사용하기에는 적합하지 않은 자료구조다.

모든 데이터가 메인 메모리에 들어있을 수는 없기 때문에 일부 데이터는 외부 디스크에 저장된다. 이 때, 디스크에 접근하는 것은 메인 메모리에 접근하는 것보다 훨씬 느리다. 그리고 디스크는 여러 개의 구역(blocks, pages)으로 나뉘어 있고, 구역 내의 특정 부분을 접근하는 것과 해당 block 전체를 접근하는 것은 동일한 시간이 걸린다.

따라서 디스크에서 데이터를 가져올 때 시간을 줄이기 위해서는, 디스크에 한번 접근해서 가져오는 데이터의 양을 늘리고, 디스크에 접근하는 횟수를 줄여야 한다.

그러나 BST 구조는 노드의 깊이에 따라 많은 노드를 순차적으로 탐색해야하기 때문에, 데이터를 디스크에 저장하게 되면 디스크 I/O가 빈번하게 발생하게 된다. (이에 대한 더 자세한 설명은 해당 블로그 참고)

AVL

BST의 불균형 문제점을 보완하기 위해 나타난 자료구조이다.

AVL 트리는 일정한 k값을 정하여 임의의 한 노드로부터 왼쪽 서브트리와 오른쪽 서브트리의 높이가 같게 유지한다.

하지만 이 방법을 사용하더라도 파일 처리에서 BST의 단점은 AVL에서도 여전히 남아있다.

Secondary Storage(주로 디스크)로부터 적은 비용에 많은 정보를 얻어오기에 한계가 있다는 점이다.

이 단점은 BST, AVL 모두 자식 노드(인덱스)가 2개 뿐이라는 특징에 있는데,

각 노드는 최대한 많은 자식 노드를 가지고 있어야 디스크 I/O가 줄어들 수 있다!

B Tree

B Tree는 이진 트리의 확장된 개념으로 나온 다진 트리(M-way Tree)의 일종으로, 이진 트리처럼 정렬을 지원하는 자료구조이다.

하나의 노드가 여러 개의 자식 노드를 가질 수 있는 트리기 때문에,

BST보다 트리의 높이를 낮춰 조금 더 빠른 탐색이 가능하며, 트리 높이가 낮을 수록 디스크 I/O 가 적어져 성능을 향상할 수 있다.

BST는 트리 뷸균형의 문제가 있지만, B Tree는 노드가 더 많은 값의 범위를 다루기에 이를 완화할 수 있다.

또한, 모든 리프 노드는 같은 레벨에 위치하여 트리가 항상 균형을 유지한다. 삽입, 삭제 등의 연산이 발생해도 트리의 구조는 효율적으로 유지된다.

B Tree는 노드 안에서 이진 탐색을 통해 키를 찾으며, 검색, 삽입, 삭제의 시간 복잡도는 O(log N)으로 일정하다.

즉, self-balancing tree로서 효율적인 검색, 삽입, 삭제 작업이 이루어지는 균형 잡힌 트리라고 볼 수 있다.

주요 특징

1. 루트 노드를 제외하고 2개 이상의 데이터를 저장할 수 있다.

2. 노드 내의 데이터는 정렬되어야 한다.

3. 노드는 가질 수 있는 자식의 제한 (최소~최대)이 존재한다.

4. 자식 포인터의 수는 항목 개수보다 하나가 많다.

더 자세한 특징은 아래 더보기 참고.

특징
1. 하나의 노드에는 2개 이상의 키가 존재할 수 있으며 항상 정렬된 상태로 저장된다.
2. 특정 노드의 차수(자식 노드의 수)가 2개 이상일 수 있고, 최대 자식 노드의 수가 M개인 B-Tree를 M차 B-Tree라고 한다.
3. M차 B-Tree는 하나의 노드에 가질 수 있는 최대 키의 개수는 M-1개이다. (만약 하나의 노드가 최대 키의 개수를 초과하면 분할 과정을 거친다.)
4. M차 B-Tree에서 특정 노드가 가질 수 있는 자식 노드의 개수는 floor(M/2)개 부터 M개다.
5. 특정 노드의 키의 개수가 K개라면 자식 노드의 수는 K+1개이다.
6. 노드의 키는 반드시 정렬된 상태여야 하고, 특정 노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 값들이, 오른쪽 서브 트리에는 큰 값들로 구성되어야 한다.
7. 루트 노드는 항상 2개 이상의 자식 노드를 가져야 한다. (단, 루트 노드가 리프 노드인 경우는 제외)
8. 최상위 노드를 루트 노드, 최하위 노드를 리프 노드, 그 사이 노드들을 브랜치 노드라고 부른다.
9. 모든 리프 노드(leaf node)들은 같은 레벨(level)에 존재해야 한다.
10. INSERT, DELETE와 같은 작업이 일어나도 항상 균형을 유지한다.

문제점

B Tree는 모든 노드에서 데이터를 저장하므로, 데이터 검색 시 내부 노드도 자주 접근하게 되어 디스크 I/O가 많아진다.

특히, 대용량 데이터일 때 성능에 영향을 미칠 수 있다.

B+ Tree

B+Tree는 B Tree의 변형된 구조로, MySQL의 InnoDB를 필두로 많은 RDBMS에서 사용하고 있는 자료구조다.

B+Tree에서 노드는 브랜치 노드(Branch Node)와 리프 노드(Leaf Node)라는 두 가지 노드로 분리된다.

특징

1. 브랜치 노드는 리프 노드의 포인터를 담아둔 key만 보유하고 있고, value(data)는 저장할 수 없다. 리프 노드는 key와 data를 모두 저장할 수 있다. 이를 통해 리프 노드들을 한번에 읽을 수 있어 디스크 I/O 효율성이 크게 향상된다.

2. 리프 노드는 브랜치 노드와 부모/자식으로 연결되어 있고, 리프 노드끼리는 형제 관계로 연결되어 있다.

B+Tree의 리프 노드들은 연결 리스트로 연결되어 있어, 범위 검색이나 순차적인 데이터 접근에 유리하다.

예를 들어, 특정 범위의 데이터를 빠르게 탐색할 수 있어, 범위 쿼리가 자주 사용되는 DB 환경에 강하다.

3. 트리가 항상 균형을 유지하므로, 검색, 삽입, 삭제의 시간 복잡도는 O(log N)으로 일정하다.

4. B+Tree는 내부 노드에 키 정보만 저장하므로, B Tree보다 더 많은 키를 한 노드에 저장할 수 있어 트리의 높이가 낮아진다.

이는 디스크에서 데이터를 읽을 때, 더 적은 레벨을 탐색하므로 성능이 더 나아진다.

Hash Table

데이터를 key와 value 쌍으로 저장하는 자료구조다. 이 자료구조는 해시 함수(Hash Function)를 사용하여 데이터를 배열의 인덱스로 매핑한다. 이를 통해 데이터 검색과 삽입을 매우 빠르게 처리 가능하다.

해시 테이블은 키 값에 대해 해시 함수를 적용하여 해시 값(Hash Value)을 계산하고, 그 값을 이용해 배열에서 해당 데이터를 저장하거나 검색한다.

Hash Function
- 입력된 키, 값을 일정한 크기의 배열 인덱스(또는 버킷)에 매핑하는 함수다. 예를 들어, 해시 함수가 주어진 키 "apple"을 0에서 9까지의 숫자로 변환하여 배열 인덱스에 저장하는 식이다.
- 해시 함수의 결과는 균등하게 분포되어야 효율이 높아지며, 키 충돌을 최소화해야 한다.

Collision Handling
- 해시 충돌은 서로 다른 키 값들이 동일한 해시 값을 가질 때 발생한다. 이 경우, 동일한 인덱스에 두 개 이상의 값이 저장되려고 하므로 충돌을 해결하는 방법이 필요하다.
1. Chaining: 배열의 각 슬롯이 linked list를 가리키도록 하여 충돌이 발생한 값들을 해당 리스트에 추가하는 방식
2. Open Addressing: 충돌이 발생하면 다른 빈 슬롯을 찾아 데이터를 저장하는 방식. 여기에는 Linear Probing, Quadratic Probing, Double Hashing 등이 있음.

장점

키에 대한 직접적인 접근을 제공하기 때문인데 해시 테이블에서 검색, 삽입, 삭제의 시간 복잡도는 O(1)이다. 해시 함수의 계산 시간이 상수 시간에 가깝기 때문이다.

단점

1. 범위 검색 불가능

해시 테이블은 정확한 값을 기반으로 검색할 때는 효율적인지만, 범위 검색에는 적합하지 않다. 예를 들어, '100 이상, 200 이하의 값'을 찾는 경우, 해시 테이블은 이러한 쿼리를 처리할 수 없다. 이 점은 DB 인덱스에서 중요한 기능이므로, 해시 테이블이 DB의 범용 인덱스로 사용되기 어려운 이유다.

2. 정렬된 데이터 접근 불가능

해시 테이블은 정렬된 순서로 데이터를 저장하지 않기 때문에 정렬된 데이터를 필요로 하는 쿼리에서는 해시 테이블은 적합하지 않다. 예를 들어, ORDER BY나 GROUP BY 와 같은 쿼리에서 해시테이블은 성능이 떨어진다.

3. 충돌로 인한 성능 저하

해시 충돌이 발생할 경우, 최악의 경우에는 O(n)의 시간 복잡도가 추가로 발생될 수 있다. 충돌 처리 방식에 따라 성능은 달라질 수 있지만 충돌이 많아질수록 성능이 저하된다. (따라서 해시 함수가 데이터를 균등하게 분포시키도록 설계를 잘 하는 것이 중요하다.)

왜 데이터베이스는 B+Tree를 주로 사용할까?

B+ Tree vs Hash Table

DB에서 정확한 키 검색(Equality Search)이 중요한 경우, 해시 테이블이 적합할 수 있다.

예를 들어, MySQL의 Memory Engine은 해시 기반 인덱스를 제공하며, MongoDB에서는 특정한 상황에 해시 인덱스를 사용할 수 있다.

MySQL의 Memory Enginedms 메모리 내에서 매우 빠른 정확한 검색이 필요할 때 적합하다. 그러나 범위 검색을 지원하지 않으므로, 데이터를 빠르게 조회하는데 있어 제약이 있을 수 있다.

MongoDB의 해시 인덱스는 특정 필드에 대한 빠른 키 검색을 지원한다. 주어진 키 값을 이용하여 목표 레코드의 주소를 직접적으로 계산하는 방식이다. 해시 함수는 내부적으로 데이터를 균등하게 분포시켜 검색 속도를 향상시킨다.
특히 등호(=) 연산에 특화되어 있으며, 값이 1이라도 다르면 다른 해시 값을 생성하기 때문에 >, < 연산이 자주 사용되는 DB 검색에 해시 테이블은 적합하지 않다.
하지만 해시 인덱스는 쿼리 검색 성능을 높이는데 사용하기 보다는 해시 샤딩을 구현하기 위해 더 많이 사용한다.

하지만 해시 테이블은 범위 검색이나 정렬이 필요한 경우에는 적합하지 않다.

해당 쿼리가 자주 사용될 경우 B+ Tree 기반의 인덱스 사용이 권장된다.

B+ Tree vs B Tree

1. 범위 검색의 효율성

범위 검색을 할 때, B Tree는 인접 노드라도 다른 서브 트리에 있다면 다시 루트 노드부터 검색을 시작해야하는데,

B+ Tree는 인접한 노드를 알 수 있기 때문에 다시 루트부터 탐색할 필요 없이 선형적으로 탐색이 가능하다.

즉, B+ Tree는 순차 검색과 범위 검색에 더 좋은 성능을 보여준다.

(+ 다만, B Tree에서 자주 access 되는 노드를 루트 가까이에 배치한다면 B Tree의 성능이 B+ Tree를 능가한다.

B+Tree는 반드시 리프노드까지 데이터를 탐색하러 가야하기 때문이다.)

2. 디스크 I/O 최적화

DB는 메모리에 모든 데이터를 저장할 수 없기 때문에 대부분의 데이터는 디스크에 저장된다.

따라서 디스크 접근이 성능에 중요한 영향을 미친다.

B+Tree는 트리의 깊이가 낮고, 리프 노드에만 데이터를 저장하는 구조 때문에 디스크 I/O 성능을 최적화 한다.

브랜치 노드에서는 키 값만 저장하므로, 트리의 높이가 줄어들고, 데이터를 찾기 위한 디스크 접근 횟수도 감소하게 된다.

메인 메모리에는 실행 중인 프로그램의 코드와 코드 실행과 관련된 데이터가 존재하는 위치이고, 보조기억장치(secondary storage)에는 프로그램과 데이터가 영구적으로 저장되는 곳으로 데이터 처리 속도가 가장 느리고, 용량이 가장 크다는 특징을 지닌다.
이때 보조기억장치는 페이지 단위*로 데이터를 읽고 쓴다. 때문에 메인 메모리에서 보조기억장치의 데이터가 필요할 때 특정 데이터만 추출하여 조회하는게 아니라 데이터가 속한 페이지 전체를 메인 메모리에 올려야 한다. 즉, 불필요한 데이터까지 읽어올 가능성이 기본적으로 존재한다.

메인 메모리에서 DB 데이터를 조회할 때, 보조기억 장치에 최대한 적게 접근하는 것이 성능면에서 좋다.
또한 연관된 데이터를 함께 모아서 저장하면 페이지 단위로 데이터를 조회할 때 불필요한 데이터가 포함될 가능성이 줄어든다. (페이지 단위에 대한 저장 공간 활용도)

* 페이지(page) 혹은 블록(block)은 파일 시스템이 디스크 및 메모리에서 데이터를 읽고 쓰는 논리적인 단위. 대표적으로 4KB, 8KB, 16KB 등의 크기를 지닌다.