알고리즘 이론 14강. B-Trees

 

[B-Trees ]

: 매우큰 데이터셋을 위한 Index 구조가 메인 메모리에 저장되지 못하는 문제가 발생.

: 이를 디스크 상에 저장하기 위해선 보다 효율적인 접근 방법이 필요했다.

: 기존의 트리들에서 탐색 시간은 아무리 작아도 logn의 시간이 필요했다.

: 트리의 height를 낮추는 방식으로 이 문제를 해결했다. ( 분기는 증가, 높이는 감소)

 

 

 

[B-Trees의 주요 아이디어]

- 높이 축소 : 기존의 이진 탐색 트리 방식대신, m-ary 탐색 트리를 사용해 높이를 축소시킨 트리이다.

 

 

 

[m-way 탐색 트리 저장 방법]

# 3-way 탐색 트리 예시

: 3-way 탐색 트리 기준으로, 각 노드는 2개의 key와 3개의 자식 노드르 가진다.

: 각 노드의 key값들의 front, middle, end 기준으로 자식 노드 위치 배분한다. (기존 트리 방식과 유사)

 

# 일반화된 트리의 노드 (m-way)

일반화된 M-way 탐색 트리 노드 구조

- 트리의 높이 : O(logmN)

 

 

 

[B-Trees 예시]

# 문제

기준 디스크 블록 크기 = 8192 바이트 key들이 32 바이트를 사용하고, 포인터가 4 바이트를 사용한다고 가정. B-Tree의 M-way의 M의 크기는?

- 노드별 공간 = 32*(M-1) + 4*M = 8192

=> M = 228 (검색 시간 축소 가능!)

 

 

 

[B-Tree의 정의]

: m에 대한 B-tree는 m-way tree 이다. (각 노드들의 자식 노드의 개수가 m개인 트리)

1. 각 잎이 아닌 노드들의 key들의 개수는 M-1개이고, 이 key들은 검색 트리의 형태로 자식 키를 칸막이로 나눈다.

2. 모든 잎노드들은 같은 level에 존재한다.

3. 모든 잎노드가 아닌 노드들은 적어도 ceil(m/2)의 자식노드를 가진다.

4. 루트는 잎노드이거나 아니면 2에서 m개의 자식노드를 가진다.

5. 잎노드는 적어도 m-1개의 key들을 가진다.

 

 

[B-Tree의 분석]

# m과 높이 h의 B-Tree에서 아이템 개수의 최대값.

Root : m-1 level 1 : m(m-1) level 2 : m^2(m-1) ... level h : m^h(m-1)

: 결국 최종 아이템의 총 개수 : m^(h+1) -1 이다.

 

 

 

[개선된 B-Tree]

: 기존의 B-Tree의 문제점은, 오직 반밖에 차지 않는다. (공간 낭비)(key값말고, 자식노드 포인터 공간때문에..)

- B*-Trees : B-Tree에서 절반이 비어 있는 문제르 해결한 트리

- B+-Trees : 더욱 효율적인 접근 방법을 제공