[DB] B-Tree 가 DB 인덱스(Index) 로 사용되는 이유

Database 의 특징

• DB 는 secondary storage(ssd, hdd 등) 에 저장된다(데이터들을 영구적으로 저장해야 하므로 당연함)
• DB 에서 데이터를 조회할 때, secondary storage 에 최대한 적게 접근하는 것이 성능 면에서 좋다.
• block 단위로 읽고 쓰기 때문에 연관된 데이터를 모아서 저장하면 더 효율적으로 읽고 쓸 수 있다.

B-Tree 계열의 장점

1. 디스크 I/O 효율성

B-Tree 계열의 특징

• B-Tree 는 각 노드에 여러 개의 키를 저장할 수 있으며, 자식 노드에 대한 포인터도 함께 저장된다.
• 데이터베이스에서 B-Tree 는 한 노드를 한 번의 디스크 읽기로 가져올 수 있도록 설계된다. 즉 한 번의 디스크 I/O 로 다수의 키를 탐색할 수 있다.
• 트리의 높이가 낮기 때문에 루트에서 리프까지 탐색 시 디스크 I/O 횟수가 줄어든다.

Self-Balancing BST 의 단점

• Self-Balancing BST(예: AVL, Red-Black 트리)는 각 노드에 하나의 키만 저장하므로, 탐색 과정에서 트리의 높이만큼 디스크 I/O 가 발생한다.
• 트리의 높이가 O(log⁡n) 이지만, 노드 개수가 많아지면 트리의 깊이가 증가하여 I/O 비용이 증가할 수 있다.

2. 낮은 트리 높이

B-Tree 계열의 장점

• B-Tree 는 각 노드에 최대 m-1 개의 키를 저장하므로, 같은 데이터를 저장할 때 트리의 높이가 Self-Balancing BST 보다 낮다.
• 낮은 트리 높이는 탐색, 삽입, 삭제 시 필요한 연산 횟수를 줄여준다.

Self-Balancing BST 의 단점:

• Self-Balancing BST 는 각 노드에 하나의 키만 저장하므로, 동일한 데이터 집합에 대해 트리의 높이가 더 높아진다.
• 트리의 높이가 높아질수록 탐색, 삽입, 삭제 시 비용이 증가한다.

3. 순차 접근의 효율성

B+Tree 의 장점

• B+Tree 에서는 리프 노드들이 연결 리스트로 연결되어 있으므로, 순차적으로 데이터를 읽는 것이 매우 효율적이다.
• 이는 데이터베이스에서 범위 쿼리(예: WHERE age BETWEEN 20 AND 30)를 처리하는 데 매우 유리하다.

Self-Balancing BST 의 단점

• Self-Balancing BST 에서는 중위 순회를 통해 순차 접근이 가능하지만, 노드 간의 연결이 없으므로 범위 쿼리를 처리할 때 효율이 떨어진다.

4. 삽입/삭제 시의 안정성

B-Tree 계열의 장점

• B-Tree 는 노드 분할(Split) 과 병합(Merge)을 통해 삽입 및 삭제 시 트리의 균형을 유지한다.
• 이러한 연산은 상대적으로 효율적이며, 트리의 높이가 낮으므로 성능이 안정적이다.

Self-Balancing BST 의 단점

• AVL 트리나 Red-Black 트리와 같은 Self-Balancing BST 는 삽입/삭제 시 트리의 균형을 맞추기 위해 많은 회전(Rotation)이 필요할 수 있다.
• 이 과정은 데이터베이스와 같이 대규모 데이터를 처리할 때 부담이 될 수 있다.

5. 메모리 및 저장 공간 사용

B-Tree 계열의 장점

• B-Tree 는 각 노드에 다수의 키를 저장하므로, 메모리와 디스크의 공간을 더 효율적으로 활용한다.
• 한 번의 디스크 I/O 로 여러 키를 읽어올 수 있으므로, 데이터베이스 인덱스에서 매우 유리하다.

Self-Balancing BST 의 단점

• Self-Balancing BST 는 각 노드에 하나의 키만 저장하므로, 동일한 데이터를 저장할 때 더 많은 노드가 필요하다.
• 이는 저장 공간과 디스크 I/O 의 비효율로 이어질 수 있다.

결론

B-Tree 계열의 장점:

1. 디스크 I/O를 최소화하여 대규모 데이터를 처리하는 데 적합.
2. 낮은 트리 높이로 탐색, 삽입, 삭제 성능이 효율적.
3. 순차 접근이 효율적이며, 범위 쿼리에 유리.
4. 메모리와 디스크 공간을 더 효율적으로 사용.

Self-Balancing BST의 단점:

• 디스크 기반 환경에서 노드가 너무 세분화되어 디스크 I/O가 많이 발생.
• 트리 높이가 더 높아질 수 있어 연산이 비효율적.

이러한 이유로 B-Tree 계열은 디스크 기반의 데이터베이스 인덱스에서 선호된다.

Self-Balancing BST 와 B-Tree 의 노드 저장 형태

공통점: 노드의 분산 저장

Self-Balancing BST 와 B-Tree 모두 “하나의 노드가 하나의 디스크 블록에 저장”된다.

하지만 각 노드에 포함된 데이터의 양과 디스크 블록 활용 효율성에서 큰 차이가 있다.

*Self-Balancing BST 를 이용하여 디스크 블록에 저장한다고 가정할 때

Self-Balancing BST와 B-Tree의 노드와 디스크 블록 저장 방식

1. Self-Balancing BST

• 일반적인 사용
  • Self-Balancing BST(예: AVL, Red-Black 트리)는 보통 메모리 내 저장을 목적으로 설계됨
  • 메모리 중심 구조로 설계되었기 때문에, 일반적으로 각 노드가 디스크 블록(또는 페이지) 크기에 맞춰 저장되지 않음
  • 따라서 이진 탐색 트리 노드들은 일반적으로 RAM(주기억장치)에 저장됨
  • 이는 컴파일러 구현, 메모리 내 검색, 실시간 데이터 처리 등에 적합함
• 노드 크기와 디스크 블록(디스크 기반으로 구현 시):
  • Self-Balancing BST의 노드는 단일 키와 두 개의 자식 포인터(왼쪽, 오른쪽)를 저장함
  • 이 크기는 보통 16~32바이트 정도로 작음
  • 디스크 블록(보통 4KB ~ 16KB) 크기에 비해 노드 크기가 작기 때문에, 하나의 디스크 블록에 노드 하나만 저장되면 나머지 공간은 낭비됨
• 탐색 시 디스크 I/O:
  • 같은 데이터 셋을 관리한다고 가정할 때, B-Tree 보다 더 많은 노드를 생성하므로, 트리의 높이가 상대적으로 높음
  • 트리 탐색 과정에서 깊이만큼 디스크 I/O가 발생하며, 각 I/O는 단일 노드만 가져옴
  • 따라서, 트리의 높이가 커질수록 디스크 접근 횟수가 증가하고 성능이 저하됨
  • 트리의 높이가 O(log⁡n) 이더라도, 노드당 I/O 가 발생하므로 더 많은 디스크 I/O 가 필요하기 때문에 성능 저하가 심할 수 있음
  • 대규모 데이터를 다루는 데 효율적이지 않음

---

2. B-Tree

• 노드 크기와 디스크 블록:
  • B-Tree의 노드는 한 번에 여러 키(최대 m−1)와 자식 포인터(최대 m)를 저장함
  • 노드 크기가 디스크 블록 크기와 일치하도록 설계되므로, 디스크 블록을 효율적으로 사용함
  • 예를 들어, 4KB 블록 크기에서 각 키와 포인터가 각각 8바이트라면 한 노드에 최대 255개의 키와 256개의 포인터를 저장할 수 있음
• 탐색 시 디스크 I/O:
  • 트리 탐색 과정에서 각 노드에 포함된 키를 활용해 탐색 범위를 크게 줄일 수 있으므로, 트리의 높이가 낮아지고 디스크 I/O 횟수가 감소함
  • 한 번의 디스크 I/O로 여러 키를 처리할 수 있어 성능이 뛰어남

주요 차이 정리