둘 다 “작은 키는 왼쪽, 큰 키는 오른쪽”이라는 규칙으로 키를 찾아 내려가는 탐색 트리다. 가르는 질문은 “노드 하나를 읽는 값이 비싼가”다. 노드를 읽을 때마다 디스크를 한 번 읽어야 하면, 노드 하나에 키를 많이 담아 트리를 낮추는 쪽이 이긴다.
어느 쪽일까
C1 (a) 키 100만 개짜리 색인이 디스크에 있고, 찾을 때마다 노드를 디스크에서 읽어 와야 한다. (b) 키 1,000개를 주기억장치에만 두고 찾는다. 디스크는 쓰지 않는다. 어느 쪽인가?
답: (a) B-트리. 키 100만 개면 가장 고르게 균형 잡힌 이진 탐색 트리도 높이가 19라 디스크를 스무 번 가까이 읽는다. 최소 차수 \(t = 100\)인 B-트리는 높이가 2다. (b) 이진 탐색 트리로 충분하다. 노드를 읽는 값이 싸면 노드를 크게 만들 까닭이 없다.
이유: B-트리가 줄여 주는 것은 디스크를 읽는 횟수다. 주기억장치 안에서 견주는 횟수는 둘 다 \(\lg n\)쯤으로 비슷하다(B-트리 검색의 표)1.
C2 (c) “새 키를 넣을 때마다 그 키만 담은 새 잎을 만들어 매단다.” (d) “키를 계속 넣었더니 맨 위 노드가 새로 생기고 모든 잎이 한꺼번에 한 칸씩 깊어졌다.” 각각 어느 쪽의 이야기인가?
답: (c) 이진 탐색 트리. B-트리는 새 잎을 만들지 않고 이미 있는 잎에 넣는다. 새 잎을 매달면 그 잎만 깊어져 잎의 깊이가 달라지기 때문이다. (d) B-트리. 가득 찬 뿌리가 쪼개지면 새 뿌리가 위에 얹힌다. 이진 탐색 트리는 뿌리가 그대로이고 새 잎이 달린 길만 길어진다.
결정적 차이
| 이진 탐색 트리 | B-트리 | |
|---|---|---|
| 노드 하나의 키 | 1개 | 여러 개. 뿌리가 아니면 \(t - 1\)개부터 \(2t - 1\)개까지 |
| 한 노드에서 고르는 길 | 2갈래 | \(x.n + 1\)갈래(\(x.n\)은 그 노드의 키 수) |
| 새 키가 들어가는 곳 | 새로 만든 잎 | 이미 있는 잎. 가득 차 있으면 먼저 쪼갠다 |
| 자라는 쪽 | 아래. 잎 밑에 잎이 달린다 | 위. 뿌리가 쪼개질 때만 높아진다 |
| 잎의 깊이 | 제각각일 수 있다. 맞추려면 레드-블랙 트리처럼 따로 고치는 규칙이 필요하다 | 늘 모두 같다 |
| 작은 예에서 맨 아래 키를 찾는 디스크 읽기 | 5번 | 2번 |
| 키 100만 개일 때 높이 | 가장 고를 때 19 | \(t = 100\)이면 2 |
디스크 읽기 5번과 2번은 B-트리의 예시에 나온 수로, 뿌리가 주기억장치에 있다고 보고 센 것이다. 마지막 줄은 높이의 식에 수를 넣은 것이다1. 선택을 가르는 줄은 “노드 하나의 키”다. 나머지 줄은 거기서 따라 나온다. 노드에 키를 여럿 담으니 갈림길이 많아지고, 갈림길이 많으니 트리가 낮아진다. 낮은 트리를 계속 낮게 두려고 잎의 깊이를 맞추고, 깊이를 맞추려고 새 잎을 달지 않고 쪼갠다.