18. B-Trees

B-트리는 디스크나 직접 접근 이차 저장소에 걸맞는 균형 탐색 트리이다. 이는 레드-블랙 트리와 비슷하지만, 디스크 입출력 연산을 최소화하는 데 최적화되어 있다. 많은 데이터베이스는 B-트리나 그 변형을 이용한다. B-트리는 자식의 수를 여러 개 가질 수 있다는 점에서 레드-블랙 트리와 다르다. 모든 n-노드 B-트리는 높이가 O(\lg n)이 된다는 점에서는 레드-블랙 트리와 비슷하다. 따라서 많은 동적 집합 연산을 O(\lg n)에 지원할 수 있다. 이는 이진 탐색 트리를 일반화한다.

Data structures on secondary storage

일차 메모리 (메인 메모리)는 대개 실리콘 메모리 칩으로 이루어진다. 많은 컴퓨터들은 마그네틱 디스크에 기반한 이차 저장소를 가진다. 이는 대개 일차 메모리보다 크다. 디스크는 공통의 을 중심으로 회전하는 하나 이상의 접시로 이루어져 있다. 디스크는 접시에 의 끝에 달린 머리를 통해 자취를 그려 읽고 쓴다. 대기 시간을 분할 상환하기 위해, 정보는 동일한 크기의 페이지로 분할되어 저장된다. 이 때 사용되는 자료구조가 B-트리이다.

18.1. Definition of B-trees

단순함을 위해, 추가 정보는 키와 같은 노드에 저장되어 있다고 가정한다. B+-트리는 추가 정보를 전부 리프 노드에 저장하는 변형이다. B-트리는 다음의 특성을 가지는 트리이다:

  1. 모든 노드 x가 다음 특성을 만족한다.
    a. 노드 x는 x에 저장된 키의 개수인 x.n을 저장한다.
    b. x.n개의 키들은 감소하지 않는 순서로 저장되어 있다.
    c. x가 리프인지 아닌지를 나타내는 불리언 값 x.leaf를 저장한다.
  2. 모든 내부 노드 x는 자식들에 대한 x.n + 1 개의 포인터를 갖는다.
  3. x의 키들은 부분 트리에 저장된 키들의 범위를 분할한다.
  4. 모든 리프들의 깊이는 같다.
  5. 노드가 가질 수 있는 키의 개수에 상한과 하한이 있다. B-트리의 최소 차수 t \geq 2를 다음과 같이 표현한다.
    a. 루트를 제외한 모든 노드는 최소 t – 1개의 키를 갖고 있어야 한다. 즉, 모든 내부 노드는 최소 t개의 자식을 갖는다. 트리가 공집합이 아니라면 루트는 최소 1개의 키를 갖는다.
    b. 모든 노드는 최대 2t – 1개의 키를 갖는다. 즉, 모든 내부 노드는 최대 2t개의 자식을 갖는다. 2t – 1개의 키를 가지는 노드를 이라 한다.

t = 2일때를 2-3-4 트리라 한다.

The height of a B-tree

Theorem. n \geq 1이면 최소 차수 t \geq 2와 n개 노드를 가진 B-트리의 높이 h는 h \leq \log_{t} \frac{n+1}{2}를 만족한다.

그러므로 트리의 높이는 O(\lg n)이다. 실제로는 레드-블랙 트리보다 훨씬 작다.

18.2. Basic operations on B-trees

Searching a B-tree

B-트리에서의 탐색은 이진 탐색 트리와 비슷하나 가지 선택의 수가 다르다. 이는 다음과 같다.

B-TREE-SEARCH(x, k)
i = 1
while i ≤ x.n and k > x.key_i
    i += 1
if i ≤ x.n and k == x.key_i
    return (x, i)
else if x.leaf
    return NIL
else DISK-READ(x, c_i)
    return B-TREE-SEARCH(x.c_i, k)

전체 시간은 O(t \log_{t} n)이다.

Creating an empty B-tree

빈 B-트리를 만드는 법은 다음과 같다.

B-TREE-CREATE(T)
x = ALLOCATE-NODE()
x.leaf = TRUE
x.n = 0
DISK-WRITE(x)
T.root = x

이는 O(1) 시간이 걸린다.

Inserting a key into a B-tree

키를 B-트리에 삽입하는 것은 이진 탐색 트리보다 훨씬 어렵다. 풀 노드를 중앙값 키를 중심으로 분할해야 한다.

Splitting a node in a B-tree

분할은 풀이 아닌 내부 노드 x와 풀인 내부 노드 x.c_i를 필요로 한다. 이는 다음과 같다.

B-TREE-SPLIT-CHILD(x, i)
z = ALLOCATE-NODE()
y = x.c_i
z.leaf = y.leaf
z.n = t - 1
for j = 1 to t - 1
    z.key_j = y.key_(j + t)
if not y.leaf
    for j = 1 to t
        z.c_j = y.c_(j + t)
y.n = t - 1
for j = x.n + 1 downto i + 1
    x.c_(j + 1) = x.c_j
x.c_(i + 1) = z
for j = x.n downto i
    x.key_(j + 1) = x.key_j
x.key_i = y.key_t
x.n += 1
DISK-WRITE(y)
DISK-WRITE(z)
DISK-WRITE(x)

이는 \Theta(t) 시간이 걸린다.

Inserting a key to a B-tree in a single pass down the tree

트리에 키를 삽입하는 방법은 다음과 같다. 시간은 O(t \log_{t} n)이 걸린다.

B-TREE-INSERT(T, k)
r = T.root
if r.n == 2t - 1
    s = ALLOCATE-NODE()
    T.root = s
    s.leaf = FALSE
    s.n = 0
    s.c_1 = r
    B-TREE-SPLIT-CHILD(s, 1)
    B-TREE-INSERT-NONFULL(s, k)
else
    B-TREE-INSERT-NONFULL(r, k)
B-TREE-INSERT-NONFULL(x, k)
i = x.n
if x.leaf
    while i ≥ 1 and k < x.key_i
        x.key_(i + 1) = x.key_i
        i -= 1
    x.key_(i + 1) = k
    x.n += 1
    DISK-WRITE(x)
else
    while i ≥ 1 and k < x.key_i
        i -= 1
    i += 1
    DISK-READ(x, c_i)
    if x.c_i.n == 2t - 1
        B-TREE-SPLIT-CHILD(x, i)
        if k > x.key_i
            i += 1
    B-TREE-INSERT-NONFULL(x.c_i, k)

18.3. Deleting a key from a B-tree

트리의 삭제는 다음과 같다. 역시 시간은 O(t \log_{t} n)이 걸린다.

  1. 키 k가 노드 x에 있고 x가 리프면 k를 x로부터 지운다.
  2. 키 k가 노드 x에 있고 x가 내부 노드라면 다음을 따른다:
    a. x에서 k 바로 앞의 자식 y가 최소 t개의 키를 가지고 있다면 y를 루트로 하는 부분 트리에서 k의 바로 앞에 있는 키 k’를 찾는다. 재귀적으로 k’를 지우고 x에서 k를 k’로 치환한다.
    b. y가 t개 미만의 키를 가지고 있다면 x에서 k 바로 뒤의 자식 z를 찾는다. z가 최소 t개의 키를 가지고 있다면 z를 루트로 하는 부분 트리에서 k의 바로 뒤에 있는 키 k’를 찾는다. 재귀적으로 k’를 지우고 x에서 k를 k’로 치환한다.
    c. y, z가 전부 t – 1개의 키를 갖고 있다면 k와 z를 전부 y로 병합시킨다. 이러면 y는 2t – 1개의 키를 갖게 된다. 이후 재귀적으로 k를 y에서 삭제한다.
  3. 키 k가 노드 x에 없다면 키 k가 트리에 있다는 가정 하에 키 k를 포함하는 부분 트리 x.c_i를 찾는다. x.c_i가 t – 1개의 키를 가지고 있다면 다음의 과정 중 하나를 수행한다. 이후 x의 적절한 자식에 재귀적으로 알고리즘을 수행하면 된다.
    a. x.c_i가 t – 1개의 키를 가지고 있으나 바로 옆의 형제가 t개 이상의 키를 갖고 있다면, x의 키 하나를 x.c_i에 주고, x.c_i의 바로 옆의 형제의 키를 x에 주고, 형제의 적절한 자식 포인터를 x.c_i로 이동시킨다.
    b. x.c_i와 x.c_i의 양 옆 형제 모두가 t – 1개의 키를 갖고 있다면, x.c_i를 하나의 형제와 병합한다. 이 때, x로부터 키 하나를 병합된 노드로 내려보내 그 키가 중앙값이 되도록 한다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중