0. 서문
디스크 I/O의 기본 단위는 블록이다. 디스크로부터 데이터를 읽거나 기록할 때 이를 포함하는 디스크 블록 전체를 메모리로 읽어오고 다시 블록 전체를 디스크에 기록한다. 디스크에 접근하기 위한 시간을 다음과 같이 나눌 수 있다.
Access time = seek time + latency + transfer time;
1. seek time : 디스크 헤드를 정확한 트랙 위로 이동시키는 시간.
2. latency : 디스크를 회전시켜 해당 블록이 디스크 헤드 아래로 오게 하는 시간. (전체 접근 시간의 50%정도 차지)
3. transfer time : 디스크 블록을 메모리로 전송하는 시간.
보통 디스크 접근 시간 단위가 milli-second 단위인데 CPU는 mirco-second나 nano-second 단위로 일을 처리한다. 즉 디스크보다 CPU가 적어도 약 1000~1000000배 빠르다는 얘기며 이렇게 느린 디스크 I/O를 위해 색인(index) 구조인 B-Tree 형제들(B*트리, B+트리, R트리...)이 탄생했다. 물론 요즘은 얘네들도 많이 개량되어 쓰이고 있다고 하는데 어떻게 얼마나 개량이 되었는지는 모르겠다.
(B-Tree에서 B는 일반적으로 balanced라는 의미로 해석이 되고 있으나 막상 Bayer가 발표한 논문에 보면 'B'에 대한 풀이 설명이 없다고 한다. Bayer의 B인지, Bayer가 당시 몸담고 있었던 Boeing사의 B인지, Balanced의 B인지 확실친 않지만 B-Tree가 일단 balanced의 성격을 띄고 있기 때문에 많은 사람이 B(alanced)-Tree의 의미로 받아 들이고 있는 듯 하다. 뭐 어째뜬 B-Tree는 B-Tree다 그냥 -_-)
Index(색인)가 가져야 할 특성에 대해 잠시 살펴보면 아래와 같다.
1. 일반적으로 보조 기억 장치에서의 탐색은 시간적인 부하가 많이 걸리기 때문에 탐색을 쉽게 하기 위해 file과는 별도로 index를 만들어 사용한다.
2. Index가 커질 경우 index 역시 보조 기억 장치에 저장하는데 보조 기억 장치는 상대적으로 느리므로 보조 기억 장치의 access 회수를 최대한 억제시켜야 한다.
3. Index에의 access 회수를 줄이기 위해서는 최대 탐색 길이 즉, 트리의 높이를 줄여야 한다.
4. 높이를 낮추기 위해서는 하나의 노드에서 나가는 branch의 개수를 증가시킨다.
아래 정리부터는 비교적 엑기스만 깔끔하게 정리되어 있는 Tong - 구태완님의 Funny Things통 의 설명과 적절히 섞어 정리하였다.
1. B-Tree의 정의
B-Tree의 중요한 특성 중 하나는 노드의 크기이다. 노드의 크기는 디스크 블록의 크기와 같게 조정될 수 있다. 따라서 노드에 저장할 수 있는 데이터의 양은 꽤 큰 편이다.
차수가 m인 B-Tree는 다음과 같은 기본적인 정의를 만족시키는 균형 잡힌 M-원 트리이다.
1. 각 node는 최대 m개, 최소 (m/2)개의 서브트리를 가져야 한다.
===> 이 조건에 의해 트리의 각 노드가 적어도 반 이상은 key값으로 채워져 있도록 한다. 따라서 서브트리가 없는 노드가 발생하지 않고 key값이 가능한 효율적으로 서브트리에 분배될 수 있도록 한다.
2. Root 노드는 최소한 두 개의 서브트리를 가져야 한다. (단 트리에 root 만 있을 경우 서브트리는 없다)
===> 이 조건에 의해 tree가 처음부터 분기하도록 한다.
3. 모든 leaf 노드는 같은 레벨에 있어야 한다. (즉, 모든 leaf 노드는 root로부터 같은 거리에 있어야 한다)
===> 모든 leaf 노드가 root로부터 같은 거리에 있으므로 어느 leaf 노드를 탐색하든 처리 횟수가 같도록 한다.
4. 각 leaf 노드의 key 값의 개수는 최소 (m/2)-1개, 최대 m-1개이다.
위 정의들을 토대로 정리하면, B-트리는 최소한 반 이상 차있으며 가급적 낮은 레벨을 지향하며 완전 균형 트리이다.
2. m의 선택
디스크에의 접근 회수를 감소시키기 위해서는 높은 차수의(즉 트리의 레벨이 낮아 탐색 경로가 짧은) B-Tree를 사용하는 것이 바람직하다. 하지만 하나의 level만을 가지는 B-Tree (m = N+1)의 경우 메모리에 모든 key 값을 가져야 하므로 비효율적이다. 따라서 전체 탐색 시간을 줄일 수 있는 m을 선택하여야 한다.
최대 탐색 시간을 구하는 공식은 아래와 같다고 한다.
g [ { (a+d) / log2m } + {(dm) / log2m)} + (1000c) ]
g : f * log2{(N+1)/2} f : 임의의 상수
c : 임의의 상수 d : 임의의 상수
a = 탐색시간 + 회전지연시간
b = {Key 값의 문자수 + (record 의 주소를 나타내는 field의 크기 * 2)} * 문자당 전송시간
ex) key 값이 최대 6문자, record 주소가 3문자일 경우 탐색 시간은 1/100 sec, 회전 지연 시간은 1/40 sec로 계산.
3. B-tree의 연산
3.1 key 값의 순차적 처리 (순회 or 탐색)
B-Tree는 각 노드를 중위 순회(inorder) 하여 key 값을 순회할 수 있다. 하지만 각 노드는 여러 개의 key 값이 있기 때문에 각각의 노드를 여러번 방문하게 된다. 따라서 순회에서는 좋은 성능을 나타내지 못한다. B-Tree의 변형 구조(특히 B+ 트리)에서는 좋은 성능을 기대할 수 있다.
3.2 Insertion
삽입/삭제 후에도 B-Tree는 B-Tree의 성질을 보존해야 하며 균형을 이루어야 한다. => 균형 algorithm 필요.
삽입 연산은 트리를 구성하는 방법(strategy)를 바꾸면 쉽게 구현될 수 있다. 이진 탐색 트리에서는 위에서 아래로(top-down) 노드를 삽입하지만, 트리가 항상 위에서 아래 방향으로 성장되다 보면 불균형 트리가 될 수 있다. B-Tree에서는 트리를 위->아래의 방법을 이용할 수 없고 아래->위 방법으로 트리를 성장시켜 간다.
1) 규칙
1. Key 값은 항상 leaf 노드에서만 삽입된다.
2. 새로운 key 값이 삽입된 노드의 현재 key 값의 개수에 따라...
2-1. 해당 노드가 가득차지 않았을 때 : 단순히 삽입 후 key 값으로 정렬.
2-2. 해당 노드가 가득찼을 때 : 해당 노드를 분열하여 원래 노드의 중간 key 값을 부모 노드로 보내고 나머지 key 값들을 둘로 나누어 각각 분열된 두 노드로 옮긴다.
2.3. Root 노드가 가득차 있는 경우 : 새로운 루트 노드와 기존 루트 노드의 형제노드를 생성. Leaf 노드에서 key 삽입 후 2.2와 같이 분열, 그 뒤 부모 역시 가득찬 경우 부모를 분할하게 되는데 결과로 2개의 B-Tree 생성된다. (분리하지 않으면 트리의 차수가 깨짐) 2개의 B-Tree를 하나로 합치기 위해 2개의 루트 노드의 가운데 key 값을 합쳐진 B-Tree 루트 노드로 보낸다. 결과적으로 B-Tree의 높이가 증가하게 되며 이 경우가 유일하게 높이를 증가시키는 경우이다.
*** 아래 예시에서 0은 노드의 비어있는 key를 의미한다.
예1) [12, 0, 0, 0]의 부모 노드 P + [5, 8, 0, 0] 1C 노드 + [13, 15, 0, 0] 2C 노드 <<<--- 6 삽입
: key 6이 들어갈 노드 1C가 가득차있지 않으므로, [5, 8, 6, 0] -> [5, 6, 8, 0]으로 단순 삽입.
예2) [12, 0, 0, 0]의 부모 노드 P + [2, 5, 7, 8] 1C 노드 + [13, 15, 0, 0] 2C 노드 <<<--- 6 삽입
: key 6이 들어갈 노드 1C가 가득찼으므로, 1C 노드는 다음과 같이 분열된다. 우선 [2, 5, 6, 7, 8] 의 중간 값인 6이 부모 노드로 보내고 남은 2, 5, 7, 8을 2개의 노드로 분리/삽입한다. 그러면 P는 [6, 12, 0, 0]이 될 것이며 자식 노드는 3개가 되어 [2, 5, 0, 0] 1C, [7, 8, 0, 0] 2C, [13, 15, 0, 0] 3C의 형태를 이루게 된다.
삽입시 평균적인 B-Tree의 분열 회수는 다음과 같다.
[분열 회수 = 1 / ((m / 2) - 1)], m=10일 때 0.25이며 m=100이면 0.02, m=1000이면 0.002와 같다. 노드의 용량이 커서 m이 커질수록 분할은 훨씬 덜 발생한다. 트리의 높이가 높을수록, 노드들의 key 보유율이 높을수록 분열 회수는 증가하게 된다.
2) 특징
1. Leaf 노드에서 삽입되고 root 노드에서 자란다.
2. 한 노드가 분열되면 반만 채워진 두 개의 노드가 생기므로 그 이후의 삽입은 분열 없이도 수행될 가능성이 높다. 즉, 한 번의 분열에 의해 여러 번의 단순 삽입이 가능해진다.
3. 부모 노드로 올라가는 key 값은 중간 값이므로 어떤 순서로 삽입하든 관계없이 트리의 균형을 개선시킬 가능성이 높다.
3.3 Deletion
삭제 연산은 항상 leaf 노드에서 이루어진다. 삭제하려는 key 값이 leaf가 아닌 노드에 있다면 후행 key 값과 자리를 바꾸어 leaf 노드로 옮긴 후 삭제한다 (복사를 통한 삭제). 연산 결과 최소한의 key 값 ((m / 2) - 1)을 갖지 못한다면(underflow가 발생하면) 재배치(redistribution)나 합병(merge, concatenation)을 수행하여 key 값 개수를 조정한다.
3.3.1 재배치(redistribution)
1. 해당 노드의 좌측 또는 우측 노드에 최소 key 개수보다 많은 key를 갖고 있을 때 사용한다.
2. 선택된 형제 노드로부터 부모 노드를 경유하여 key 값을 해당 노드로 이동한다.
3. 하나 이상의 key 값을 이동시켜서 (부모 노드와 형제 노드, 해당 노드의 key 값 중, 중간 값을 부모 노드로 보내고 나머지를 2개로 나누어 할당한다.) key 값의 분포를 균형 있게 유지하여 트리의 성능을 개선할 수 있다.
4. Tree 구조의 변경은 없다.
3.3.2 합병 (merge, concatenation)
1. 재배치가 불가능한 경우 사용.
2. 삽입시 분열의 반대 과정.
3. 부모 노드와 형제 노드의 key 값과 해당 노드의 key 값을 하나의 노드로 합병.
4. 합병 당한 두 노드 중 하나를 새로 만들어진 노드로 대치하고 나머지 하나는 제거한다.
5. 최악의 경우 root 노드까지도 변경될 수 있다.
6. Tree의 구조가 변경된다.
여기까지 B-Tree의 일반적인 특성과 순회, 삽입, 삭제 과정을 알아봤다. B-Tree는 최소한 반 이상 차 있어야 하므로, 노드의 반에 해당 하는 공간이 낭비되는 현상이 발생할 수 있다. 그러나 시뮬레이션을 통한 결과 트리에 있는 key 값들의 개수가 안정되는 시점에 이르렀을 때 노드들은 약 69%가 차 있음이 밝혀졌다. 즉, 평균 저장공간 사용률이 69%이라는 얘기다.
썩 높지 않은 저장공간 사용률과 순회에 적합하지 않는 B-Tree를 보완하기 위해 변형된 B-Tree들이 등장하였다. B* 트리는 저장공간 사용률을 높였으며 B+ 트리는 순회 능력을 끌어 올린 변형 B-Tree들이다. B-Tree 계열 트리들에 대해서는 다음에 정리하겠다.
덧글 : wikipedia 영문 버전에서 "BTree" 검색어로 찾아보니 꽤 놀라웠다. 상당히 정리가 잘 되어 있었다. 구글링을 해서 얻을 수 있는 어지간한 웹페이지보다 설명이 잘 되어 있었다. 뭐 한글판은 형편 없었지만 :-)
2. 한 노드가 분열되면 반만 채워진 두 개의 노드가 생기므로 그 이후의 삽입은 분열 없이도 수행될 가능성이 높다. 즉, 한 번의 분열에 의해 여러 번의 단순 삽입이 가능해진다.
3. 부모 노드로 올라가는 key 값은 중간 값이므로 어떤 순서로 삽입하든 관계없이 트리의 균형을 개선시킬 가능성이 높다.
3.3 Deletion
삭제 연산은 항상 leaf 노드에서 이루어진다. 삭제하려는 key 값이 leaf가 아닌 노드에 있다면 후행 key 값과 자리를 바꾸어 leaf 노드로 옮긴 후 삭제한다 (복사를 통한 삭제). 연산 결과 최소한의 key 값 ((m / 2) - 1)을 갖지 못한다면(underflow가 발생하면) 재배치(redistribution)나 합병(merge, concatenation)을 수행하여 key 값 개수를 조정한다.
3.3.1 재배치(redistribution)
1. 해당 노드의 좌측 또는 우측 노드에 최소 key 개수보다 많은 key를 갖고 있을 때 사용한다.
2. 선택된 형제 노드로부터 부모 노드를 경유하여 key 값을 해당 노드로 이동한다.
3. 하나 이상의 key 값을 이동시켜서 (부모 노드와 형제 노드, 해당 노드의 key 값 중, 중간 값을 부모 노드로 보내고 나머지를 2개로 나누어 할당한다.) key 값의 분포를 균형 있게 유지하여 트리의 성능을 개선할 수 있다.
4. Tree 구조의 변경은 없다.
3.3.2 합병 (merge, concatenation)
1. 재배치가 불가능한 경우 사용.
2. 삽입시 분열의 반대 과정.
3. 부모 노드와 형제 노드의 key 값과 해당 노드의 key 값을 하나의 노드로 합병.
4. 합병 당한 두 노드 중 하나를 새로 만들어진 노드로 대치하고 나머지 하나는 제거한다.
5. 최악의 경우 root 노드까지도 변경될 수 있다.
6. Tree의 구조가 변경된다.
여기까지 B-Tree의 일반적인 특성과 순회, 삽입, 삭제 과정을 알아봤다. B-Tree는 최소한 반 이상 차 있어야 하므로, 노드의 반에 해당 하는 공간이 낭비되는 현상이 발생할 수 있다. 그러나 시뮬레이션을 통한 결과 트리에 있는 key 값들의 개수가 안정되는 시점에 이르렀을 때 노드들은 약 69%가 차 있음이 밝혀졌다. 즉, 평균 저장공간 사용률이 69%이라는 얘기다.
썩 높지 않은 저장공간 사용률과 순회에 적합하지 않는 B-Tree를 보완하기 위해 변형된 B-Tree들이 등장하였다. B* 트리는 저장공간 사용률을 높였으며 B+ 트리는 순회 능력을 끌어 올린 변형 B-Tree들이다. B-Tree 계열 트리들에 대해서는 다음에 정리하겠다.
덧글 : wikipedia 영문 버전에서 "BTree" 검색어로 찾아보니 꽤 놀라웠다. 상당히 정리가 잘 되어 있었다. 구글링을 해서 얻을 수 있는 어지간한 웹페이지보다 설명이 잘 되어 있었다. 뭐 한글판은 형편 없었지만 :-)
덧글|덧글 쓰기|신고