데이터베이스 저장에 왜 B-tree 자료구조가 필요할까?

 

디스크 소개

 

 

디스크는 플래터(platter)와 스핀들(spindle)로 구성되어 있으며, 헤드(head)가 데이터를 읽고 쓴다.

디스크에서 데이터를 읽기 위해서는

1. 플래터가 회전해서 해당 데이터에 접근하고,
2. 헤드가 중심에서 가장자리로 이동해서 정확한 트랙에 도달하면 원하는 데이터를 읽는다.

 

그런데 이런 기계적인 움직임 때문에 디스크 접근은 매우 느리다.

 

 

 

 

게다가 현실세계에서는 점점더 메모리 요구량이 커지고 있다.

큰 용량의 데이터를 저장하려면 디스크와 같은 보조 저장 장치에 저장해야하는데,

기계적인 움직임으로 인해 보조 저장 장치에 저장된 데이터에 접근하는 속도는 메인 메모리보다 느리다.

 

 

비록 보조 저장 장치는 용량이 크지만 메모리보다 느리기 때문에, 효율적인 디스크 I/O가 중요하다.

그래서 이를 위한 해결 방안으로 B-Tree와 같은 자료구조를 사용해 데이터 접근 횟수를 줄이고 성능을 개선할 수 있다.

 

 

 

 

 

 

B-tree에 대해 설명하기 전에 먼저 대규모 데이터베이스 처리 과정 (Process of Handling Large Databases) 을 알아보자.

 

1. 전체 데이터베이스를 보조 저장 장치에 저장
   • 데이터베이스의 크기가 메인 메모리의 용량을 초과하기 때문에 HDD나 SSD에 저장된다.
2. 필요한 부분만 메모리에 로드 (Disk-Read(x))
   • 모든 데이터를 메모리에 불러올 수 없기 때문에, 필요한 데이터만 선택적으로 메모리에 가져온다.
     여기에서 x는 처리할 데이터에 대한 포인터를 의미한다.
3. 데이터 조작 및 처리 수행
   • 불러온 데이터의 속성 값들을 수정하거나 특정 작업을 수행한다.
4. 수정된 데이터를 보조 저장 장치에 저장 (Disk-Write(x))
   • 데이터가 변경된 경우에만 Disk-Write가 실행된다.
   • 변경이 없으면 Disk-Write는 생략된다.

 

 

 

 

보조 저장 장치(HDD/SSD)는 메모리보다 느리기 때문에 디스크 접근 횟수를 줄이는 것이 아주 중요하다.

성능의 향상을 위해서 우리는 불필요한 I/O 연산을 최소화하고, 필요한 데이터만 효율적으로 읽고 써야 한다.

 

(그래서 B-Tree와 같은 자료구조를 사용한다.
B-Tree는 한 번의 디스크 접근으로 다량의 데이터를 처리하도록 설계되어 디스크 I/O를 최적화한다. )

 

 

 

 

 

그런데 문제가 있다.

대규모 데이터베이스에 있어서, 디스크 I/O가 많을수록 성능이 저하된다.

데이터를 빠르게 찾기 위해서 엄청난 양의 인덱싱이 어렵기 때문이다.

그래서 인덱싱을 효율적으로 할 수 있는 방법을 찾아야 한다.

 

 

 

 

 

 

이진 탐색 트리 vs. B-Tree

 

기존에 사용하던 방법은 이진 탐색 트리(Binary Search Tree, Red-Black Tree)를 사용하는 것이었다.

하지만 이 방식은 각 노드에 하나의 키만 저장하기 때문에, 대규모 데이터베이스에서는 탐색 경로가 길어져서 디스크 I/O가 증가하게 된다.

위 그림에서는 필요한 데이터를 찾기 위해 5번의 디스크 I/O가 필요하다.

이진 탐색 트리는 메모리 측면에서는 적합하지만, 보조 저장 장치의 접근에서는 비효율적이다.

 

 

 

 

이런 방식을 개선하기 위해 B-Tree 방식을 채택했다.

B-Tree는 다수의 키를 한 노드에 저장할 수 있는 균형 잡힌 탐색 트리다.

위 예제에서는 루트와 두 개의 하위 노드에 걸쳐 탐색이 이루어지며 2번의 디스크 I/O만으로 데이터에 접근한다.

 

 

결국, B-Tree의 장점을 정리해보면

• I/O 최소화: 한 번의 디스크 접근으로 더 많은 데이터를 가져올 수 있다.
• 대규모 데이터베이스에 적합: 노드에 여러 키를 저장하므로 트리의 높이(깊이)가 낮아져 I/O 비용이 줄어든다.
• 균형 유지: 항상 균형을 유지하여, 데이터 추가/삭제 시에도 성능 저하를 방지할 수 있다.

 

그래서 한 번의 디스크 I/O로 여러 키를 가져올 수 있고,

각 노드는 여러 개의 키를 가지므로, 결정 경로가 더 적어 탐색이 빠르다.

• 예: 하나의 노드에서 최대 (x.n + 1) 방향의 결정을 내릴 수 있다.

 

 

 

 

B-Tree 예시

 

그림에서 B-Tree는 여러 키(예: 10, 20, 14, 17)를 가지며, 각 노드에 자식이 연결된다.

이러한 구조는 더 적은 깊이로 동일한 양의 데이터를 포함할 수 있어, I/O 비용을 절감할 수 있다.

 

 

 

 

 

 

B-Tree Properties

 

 

 

1. B-Tree 노드의 속성 (Node Attributes)

• x.n: 노드 xxx에 저장된 키의 개수를 의미한다.
• x.key₁, x.key₂, ..., x.keyₓ.ₙ: 노드에 저장된 키들이며, 오름차순으로 정렬되어 있다.
• x.leaf: 해당 노드가 리프 노드인지 여부를 나타내는 불린 값 (TRUE/FALSE).
• x.c₁, x.c₂, ..., x.cₓ.ₙ₊₁: 자식 노드에 대한 포인터
  (리프 노드에는 자식 노드가 없으므로 자식에 대한 포인터가 정의되지 않음)

 

 

 

2. 키의 범위와 서브트리 관리

• 각각의 키는 서브트리의 범위를 분리한다.
  • 예: {5} ≤ 10 ≤ {14,17} ≤ 20 ≤ {23,27}와 같은 방식으로 키들이 서브트리 사이에 정렬된다.
• 모든 리프 노드는 동일한 깊이에 위치하며, 이는 트리의 높이를 정의한다. (균형 이진 트리이기 때문)

 

 

 

3. B-Tree의 최소 및 최대 키 제한

• 최소 차수 t를 사용해서 노드에 저장할 수 있는 키의 개수에 대해 하한과 상한이 정의된다.
  • 루트가 아닌 모든 노드는 적어도 t−1개의 키를 가져야 한다.
  • 루트 노드는 적어도 하나의 키를 가져야 한다.
  • 모든 노드는 최대 2t−1개의 키를 가질 수 있다.
  • 만약 노드가 정확히 2t−1개의 키를 가지고 있다면 꽉 찬 노드(full node)라고 부른다.

 

 

 

4. B-Tree의 높이와 성능

• 트리의 높이는 디스크 I/O 횟수와 비례한다.
• 높이의 상한: 트리의 키 개수 n과 최소 차수 t에 따라 계산된다.​
  • 높이가 증가할수록 더 많은 I/O가 필요하므로, 트리의 높이를 낮게 유지하는 것이 중요함