별 잡다

B-Tree

pwerty 2025. 4. 3. 18:34

B-Tree는 자가 균형 이진 검색 트리의 일종이다.

  • 대량의 데이터를 효율적으로 저장하고 검색하는데 유용하다.
  • 데이터베이스와 파일 시스템 같은 곳에서 널리 사용된다. 주요 특징은 이렇게 있다 :
    • 자가 균형 유지 : 삽입이나 삭제 연산 후에도, 트리가 자동으로 균형을 유지하여 효율적인 검색을 보장한다.
    • 여러 키 저장 : 하나의 노드에 여러 키를 저장 할 수 있으니, 디스크 접근 횟수를 최소화 할 수 있다.
    • 넓은 분기 : 트리의 깊이를 얕게 유지한다. 따라서 검색 속도를 높인다.

디스크 접근 연사의 횟수를 최소화하는데 유리한 B-Tree는 레드 블랙 트리와 비슷하지만 노드들이 자식을 수천 개까지 가질 수 있다는 점에서 레드 블랙 트리와 다르다. 디테일하게 이야기해서, B-Tree의 "분기 인자"는 사용된 디스크의 특성에 의해 결정되지만 매우 클 수 있다.

  • 노드가 n개인 B-Tree는 높이가 모두 O(log n)이라는 점에서 레드 블랙 트리와 비슷해 많은 동적 집합(dynamic set) 연산들을 O(lg n) 시간에 구현 할 수 있다. 하지만, B-Tree는 분기 인자가 더 커 높이를 나타내는 로그의 밑이 더 크다. 이로 인해 레드 블랙 트리의 높이보다 상당히 더 작을 수 있다.
    • 여기서 논하는 동적 집합은 쉽게 말하면 데이터가 계속 변할 수 있는 집합을 뜻한다. 친구 목록은 수시로 추가되거나, 삭제되고, 특정 친구를 검색한다. 이러한 작업을 가능케하는 집합을 말한다.
  • B-Tree는 이진 검색 트리를 자연스럽게 일반화 한 것이다. 

단순한 B-트리의 예제.

  • 내부 노드 x가 x.n개의 키를 포함한다면 x는 x.n + 1개의 자식을 가진다. 노드 x에 있는 키들은 노드 x에 의해 처리되는 키의 범위를 x.n + 1개의 부분 범위로 분할하는 데 사용되는데 분할점으로 사용되는데 각 부분 범위는 x의 자식 하나가 처리하게 된다.
    B-트리에서 키를 검색할 때는 노드 x에 저장된 x.n개의 키와 비교해 (x.n + 1)가지 중 하나를 고르는 결정을 하게 된다. 내부 노드는 그 자식들에 대한 포인터들을 갖지만 리프 노드들은 갖지 않는다.


  • 각기 길이가 다른 두 개의 젓가락이 기준점이 된다고 생각하면 된다. 짧은 젓가락보다 더 짧은 영역, 긴 영역보다 더 긴 영역, 또 그 사이이의 젓가락이 있을 수 있다. 처음 두 젓가락은 분할 점 역할을 하며, 이 두 젓가락을 기준으로 범위를 좁히고 원하는 젓가락 길이를 찾아 갈 수 있게 된다는 것이다.

 

이걸 쓰는 보조 기억 장치의 자료구조

컴퓨터 시스템은 메모리 용량을 제공하는 여러 기술을 이용한다. 주 기억 장치, 메인 메모리 등 있는데, 좀 더 깊이 들어가면 HDD, SDD 가 속해있는 보조 기억 장치의 존재를 알 수 있다. 보조 기억 장치는 주 기억 장치와 비교하면 수십 배에서 수백 배의 용량을 갖는다. 이러한 디스크 드라이브가 메인 메모리에 비해서 더 싸고 용량도 훨씬 크지만, 물리적인 한계 때문에 속도는 훨씬 느리다. 보통 속도는 플레터 회전 수에 영향을 받는데, 보통 서버용이 15,000RPM | 일반 하드가 7,200 | 랩탑 용은 5,400쯤 한다.

제일 흔하게 쓰는 7,200RPM이 빠르다고 느껴져도, 한 번 회전에는 8.33ms가 걸리는데, 메인 메모리의 평균 50ns라는 접근 시간보다 10만배 이상 느린 것이다. 현 시대에서도 디스크 드라이브의 평균 접근 시간은 4밀리초 정도이다. 기계적으로 움직이는 동안 기다린 시간을 지연 시간이라고 부르는데, 분할 지불하기 위해 디스크 접근은 한 번에 여러 항목을 접근한다. 각 디스크는 읽기/쓰기는 하나 이상 블록들 전체에 대해 이루어진다. 일반적인 디스크 드라이브는 512 - 4096 바이트의 블록 크기를 가진다. 

디스크 접근 횟수는 읽거나 써야만 하는 정보의 블록 수로 측정한다. 현재 트랙과 원하는 트랙 사이의 거리와 원판의 초기 회전 상태에 달려있다. 원판 접근 시간이 일정하지 않을시라도 읽거나 쓴 블록 수는 디스크 드라이브를 접근하는 데 걸린 총 시간의 좋은 일차 근사를 제공한다. 일반적인 B-트리 응용에서 다루는 데이터의 양은 매우 크기 때문에 모든 데이터를 메인 메모리에 한 번에 올릴 수는 없다. B-트리 알고리즘은 선택된 페이지를 필요 할 때 디스크로부터 메인 메모리로 복사하고 변경된 블록들을 디스크에 다시 써넣는다. B-트리 알고리즘은 메인 메모리에 언제나 일정한 개수의 블록들만을 유지한다. 그러므로 메인 메모리 크기가 다룰 수 있는 B-트리의 크기를 제한하지는 않는다.

B-트리 프로시저들은 디스크로부터 메인 메모리로 정보를 읽기 위해서, 그리고 메인 메모리에서 디스크로 정보를 쓰기 위해서 필요하다. 어떤 객체 x에 대해 논해보자. 메인 메모리에 x가 있다면 x.key로 확인 할 수 있다. 하지만 x가디스크에 존재한다면 프로시저는 x의 속성들을 참조 할 수 있기 전에 객체 x를 포함하는 블록을 메인 메모리로 읽어 들이기 위해 Disk-Read(x) 연산이 필요하다. 비슷하게 프로시저는 객체 x의 속성들에게 일어난 어떤 변화든지 저장하기 위해 x를 포함하는 블록을 디스크에 쓸 수 있도록 Disk-Read(x)를 호출한다.
이러한 일이 일어난다 :

x = 어떤 객체에 대한 포인터
Disk-Read(x)
x의 속성들을 접근하고 수정하는 연산!!!!
Disk-Write(x) // x의 속성을 수정하지 않았다면 생략한다.
x의 속성에 접근하지만 수정하지는 않는 다른 연산들

컴퓨터 시스템은 메인 메모리에 언제나 제한된 갯수의 블록들만을 유지 할 수 있다. B-Tree 알고리즘들은 시스템이 쓰지 않는 메인 메모리 블록들을 저절로 빠지게끔 한다고 가정한다. Disk-Read와 Disk-Write 연산의 수에 의해 결정되는 것을 보면, 각각의 연산이 가능한 많은 정보를 읽거나 쓰기를 원한다. B-트리의 노드는 보통 한 개의 디스크 블록 전체만큼 크고 이 크기는 B-트리 노드가 가질 수 있는 자식의 갯수를 제한한다.

디스크 드라이브에 저장된 큰 B-Tree들은 블록 크기에 상대적인 키의 크기에 따라 50, 2000 사이의 분기 인자를 자주 가진다. 큰 분기 인자는 트리의 높이와 어떤 키든지 찾는 데 필요한 디스크 접근의 횟수를 극적으로 줄인다. 아래 그림은 키를 10억 개 이상 저장 할 수 있는 분기 인자가 1001이고 높이가 2인 B-트리이다. 루트 노드를 항상 메모리에 상주 시키면 이 트리에서 어떤 키든, 최대 두 번의 디스크 접근에서 해결 할 수 있다.

 

B-트리의 정의

모든 것을 단순화 하기 위해 이진 검색 트리와 레드 블랙 트리에서 했던 것처럼 키와 관련된 부속 정보는 키와 같은 노드에 있다고 가정한다. 실제로는 키와 관련된 부속 정보를 담고 있는 다른 디스크 블록을 가리키는 한 개의 포인터만 함께 저장하기도 한다. 이 장의 의사코드는 키가 어떤 노드에서 다른 노드로 이동 할 때, 그 키와 관련된 부족 정보, 또는 그런 부속 정보를 가리키는 포인터가 함께 이동한다고 잠정적으로 가정한다.
(이건 또 뭐야 싶지만) B+-트리로 알려진 파생형 B-트리는 리프 노드에 모든 부수적인 정보를 저장하고, 내부 노드는 키와 자식 노드를 가리키는 포인터만 저장하여 내부 노드의 분기 인자를 최대화한다.

  1. 각 노드는 여러 개의 키를 가질 수 있다.
    • 키들은 오름차순 (작은 것에서 큰 것으로) 정렬된다. [10, 20, 30]
  2. 내부 노드는 자식 노드를 가진다. 각 키는 왼쪽과 오른쪽을 구분하는 기준이다.
    • [30]이 주어진다고 하면, 30보다 작은 것, 30보다 큰 것으로 구분 할 수 있다.
  3. 모든 리프 노드는 같은 높이에 있다. 즉, 균형은 자동으로 유지된다.
  4. 노드가 가질 수 있는 키의 갯수는 제한 되어있다 : 최소 차수 t(>= 2)를 기준으로 한다.
    • 최소 : 루트를 제외한 모든 노드는 t-1개 이상의 키를 가져야 한다.
    • 최대 : 한 노드는 2t - 1개 이하의 키만 가질 수 있다.

가장 단순한 B-트리는 t = 2인 경우에 생긴다. 모든 내부 노드가 2, 3, 4개의 자식 노드를 가지므로 2-3-4 트리다.
그러나 실제로는 훨씬 더 큰 t 값으로 높이가 더 낮은 B-트리를 만들곤 한다.

B-트리의 높이

B-트리를 이용한 대부분의 연산을 위해 필요한 디스크 접근 횟수는 트리의 높이에 비례하게 된다. 다음 정리는 B-트리가 최악의 경우일 때, 높이의 상한을 보여준다.

n >= 1 일 때, 높이가 h이며 최소 차수가 t >= 2인 임의의 n개이 키글 가진  B-트리 T에서 다음이 성립한다. h <= log _t (n + 1) / 2

이 증명을 모두 쓸 수 없지만, 증명 과정에서 레드 블랙 트리와 비교 했을 때의 B-트리의 강점을 알 수 있다. 두 경우 모두 트리의 높이가 O(log n)으로 증가함에도 불구하고, B-트리는 로그의 밑이 몇 배 이상 커질 수 있다. 따라서 B-트리는 대부분의 트리 연산에서 레드 블랙 트리보다 검사해야 하는 노드의 갯수가 약 lg t배 줄어든다. 보통 한 번의 디스크 접근이 필요하므로, B-트리는 상당한 양의 디스크 접근 횟수를 줄여준다.

B-트리 기본 연산

검색

B-tree-search(x, k)
	i = 1
	while i <= x.n and k > x.key(i)
    	i = i + 1
        if i <= x.n and k == x.key(i)
        	return (x, i)
        elseif x.leaf
            return NIL
        else Disk-Read(x.c(i))
        	return B-tree-search(x.c(i), k)

비어 있는 트리 생성

B-Tree-Create(T)
	x = allocate-node()
    x.leaf = TRUE
    x.n = 0
    disk-write(x)
    t.root = x

트리에 삽입

이진 검색 트리로 키를 삽입하는 것보다 훨씬 복잡하다. 이진 검색 트리처럼 새로운 키가 삽입 될 리프의 위치를 찾는다. 하지만 B-트리에서는 단순히 새로운 리프 노드를 생성해서 키를 삽입 할 수 없다. 대신 이미 존재하는 리프 노드에 새로운 키를 삽입한다. 리프 노드가 가득차면 삽입 할 수 없으니, 중간 키 근처에서 각각 t -1 개의 키를 가지는 두 노드로 분할 하는 연산이 필요하다.

B-트리에서 노드 분할하기

B-Tree-Split-Chiled(x, i)
	y = x.c(i)		 // 분할 할 가득 찬 노드
    z = allocate-node() 		// z는 y의 반을 가진다.
    z.leaf = y.leaf
    z.n = t - 1
    for j = 1 to t - 1			// z는 y의 가장 큰 키들을 가진다.
    	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					// y는  t - 1 개의 키들을 가진다.
 for j = x.n + 1 downto i + 1	// x의 자식들을 오른쪽으로 이동한다.
 	x.c(j+1) = x.c(j)
x.c(i+1) = z					// ... z를 자식으로 만들기 위한 공간을 마련한다.
for j = x.n downto i			// x에 있는 해당되는 키들을 이동한다.
	x.key(j+1) = x.key(j)
x.key(i) = y.key(t)				// y의 중간 키를 삽입한다.
x.n = x.n + 1					// x는 자식을 얻었다.
Disk-Write(y)
Disk-Write(z)
Disk-Write(x)

트리의 아래로 향하는 단일 패스로 B-트리에 키 삽입하기

높이 h인 B-트리 T에 키 k를 삽입하는 것은 트리의 아래로 향하는 단일 단일 패스와 O(h)번 디스크 접근이 필요하다. 필요한 CPU 시간은 O(th) = O(t log(t)n)다. B-Tree-Insert 프로시저는 재귀호출로 가득 찬 노드에 내려가지 않는 것을 보장하기 위해 B-Tree-Split-Child를 사용한다. B-Tree-Insert은 만약 루트가 가득 차 있다면 다음 쪽의 B-Tree-Split-Root 프로시저를 호출하여 분할한다.

B-Tree-Insert(T, k)
	r = T.root
    if r.n == 2t - 1
    	s = B-Tree-Split-Root(T)
        B-Tree-Insert-Nonfull(s, k)
    else B-Tree-Insert-Nonfull(r, k)
B-Tree-Split-Root(T)
	s = Allocate-Node()
    s.leaf = False
    s.n = 0
    s.c(1) = T.root
   	T.root = s
    B-Tree-Split-Child(s, 1)
    return s
B-Tree-Insert-NonFull(x, k)
	i = x.n
    if x.leaf				// 리프에 삽입
    	while i >= 1 and k < x.key(i) // k에 대한 공간을 만들기 위해 x에 있는 키들을 이동
    		x.key(i + 1) = x.key(i)
    		i = i - 1
    	x.key(i + 1) = k		// x에 키 k를 삽입한다.
    	x.n = x.n + 1			// 이제 x는 키를 하나 더 가진다.
    	Disk-Write(x)
   else while i >= 1 and k < x.key(i)	// k가 속한 자식을 찾았다.
   		i = i - 1
   i = i + 1
   Disk-Read(x, c(i))
   if x.c(i).n == 2t - 1		// 만약 자식이 가득 찼으면 그 자식을 분할한다.
   		B-Tree-Split-Chile(x, i)
        if k > x.key(i)			// k가 x.c(i) 또는 x.c(i + 1)로 가는가?
        	i = i + 1
   B-Tree-Insert-Nonfull(x.c(i).k)

삭제

삭제가 삽입과 유사하면서 복잡하다. 리프 노드만이 아닌 임의의 노드에서 키가 삭제 될 수 있으며, 내부 노드에서의 키를 삭제 할 때에는 그 노드의 자식 노드를 다시 정리해야 하기 때문이다. 수도 코드 말고 과정을 설명하는게 보다 확실하겠다.

CASE 1
검색이 리프 노드 x에 도착한다. 만약 x가 키 k를 포함하면 k를 x로부터 삭제한다. 만약 x가 키 k를 포함하지 않으면 k는 B-트리에 없고 아무것도 할 필요가 없다.

CASE 2
검색이 키 k를 포함하는 내부 노드 x에 도착한다. k = x.key(i)라고 하자. x.c(i)(x의 k 바로 전 키를 갖는 자식)과 x.c(i+1)(x의 k 바로 다음 키를 갖는 자식)에 들어있는 키들의 개수에 따라서 아래의 세 가지 경우들 중에 하나가 적용된다.

  • CASE 2-A
    x.c(i)가 적어도 t개의 키를 가진다. k의 선행 키인 k'을 x.c(i)를 루트로 하는 서브 트리에서 찾는다. 재귀적으로 x.c(i)로부터 k'를 삭제하고 x에서 k를 k'으로 바꾼다. (k'은 한 번의 하향식 패스만에 찾아지고 삭제 될 수 있다.
  • CASE 2-B
    x.c(i)가 t - 1개의 키를 갖고 x.c(i+1)은 적어도 t개의 키를 가진다. 이 경우는 case 2a에 대칭적이다. k의 후행 키인 k'을 x.c(i+1)을 루트로 하는 서브 트리에서 찾는다. 재귀적으로 x.c(i+1)로부터 k'를 삭제하고 x에서 k를 k'으로 바꾼다. 이 또한 k'의 검색과 삭제는 한 번의 하향식 패스만에 가능하다.
  • CASE 2-C
    x.c(i)와 x.c(i+1)이 t - 1 개의 키를 갖는다. x가 k와 x.c(i+1)에 대한 포인터 둘 다 잃고 x.c(i)는 이제 2t - 1개의 키들을 갖도록 하기 위해서 k와 x.c(i+1)의 모든 키들을 병합하여 x.c(i)로 넣는다.

CASE 3
검색이 키 k를 포함하지 않는 내부 노드 x에 도착한다. 방문하는 각각의 노드가 적어도 t - 1개이 키들을 갖도록 하면서 트리를 아래로 검색을 계속 한다. 그렇게 하기 위해서, 만약 k가 트리에 반드시 있다면 k를 포함해야만 하는 적절한 서브 트리의 루트 x.c(i)를 알아낸다. 만약 x.c(i)이 t - 1개의 키들만 가지면 적어도 t개의 키들을 가지는 어떤 노드로 내려가는 것을 보장하기 위해, 필요에 따라 뒤에서 설명할 과정을 수행한다.

  • CASE 3-A
    x.c(i)가 단지 t - 1개의 키를 가졌으나 최소 t개의 키를 가진 인접한 형제 노드가 있다. x로부터 아래에 있는 x.c(i)에 키 하나를 이동하고, x.c(i)의 인접한 왼쪽 또는 오른쪽 옆의 형제 노드로부터 키를 x로 올려주고 그 형제로부터 연관된 자식에 대한 포인터를 x.c(i)로 옮긴다.

  • CASE 3-B
    x.c(i)와 x.c(i)의 양쪽 인접한 형제 노드가 모두 t - 1 개의 키를 가지고 있다(x.c(i))는 한 개 또는 두 개의 자식을 갖는 것이 가능하다). x.c(i)에 한 개의 형제를 병합한다. 이는 x로 부터 키 한 개를 새로 병합된 노드로 내려 보내서, 그 노드의 중간 키가 되도록 하는 것을 포함한다.

 

너무 어려운데