2008. 8. 3. 04:49 IT 자료/데이터베이스
[자료구조] M-one 탐색 Tree, B-Tree, B*-Tree, B+-Tree, TRIE
M-one 탐색 Tree, B-Tree, B*-Tree, B+-Tree, TRIE
Definition
1 m-one search tree : Binary search tree의 일반화된 형태
2 B-tree : m-one search tree 의 특수 형태이며 균형 Binary search tree의 일반 형태
3 B*-tree, B+-tree : B-tree의 변형
1. Index의 구성
l 일반적으로 보조기억장치에서의 탐색은 시간적인 부하가 많이 걸리기 때문에 탐색을 쉽게 하기 위해 file과는 별도로 index를 만들어 사용한다.
l Index가 커질 경우 Index 역시 보조기억장치에 저장하는데 보조기억장치는 상대적으로 느리므로 보조기억장치의 Access횟수를 최대한 억제시켜야 한다.
l Index에의 Access 횟수를 줄이기 위해서는 최대 탐색길이 즉, tree의 높이를 줄여야 한다.
l 높이를 낮추기 위해서는 하나의 Node에서 나가는 Branch 의 개수를 증가 시킨다.
2. m-one search tree
|
N |
P(0) |
K(1) |
P(1) |
P(2) |
K(2) |
……. |
P(n-1) |
K(n) |
P(n) |
n : Node에 있는 key 값의 개수
l 한 Node에서 나가는 Branch의 개수를 최대 m개 (m>2)인 tree이다.
l 자식 Node를 최대 m개 가지며 m-1개의 Key 값을 갖는다.
2.1 특징
l 한 Node안에 있는 Key값은 오름차순으로 정렬된다.
l P(0)가 가리키는 종속 tree의 모든 Key 값은 P(1)이 가리키는 종속 tree의 key 값보다 작다.
l P(i)가 가리키는 종속 tree도 m-one search tree이다
Cf) 한 Node안에서 특정 key 값을 찾을 때 그 Node 안에 있는 Key 값의 개수가 많다면 선형탐색보다 이진탐색이 더 효율적일 수 있다.
2.2 성능
l 높이가 h인 m-one tree에서 Node의 최대 개수는 (mh-1)/(m-1) 이다 . 각 Node가 최대 m-1개의 key값을 가지므로 tree 의 전체 key값 개수는 최대 mh-1개이다.
l 전체 key값의 개수가 N인 m-one tree가 최대 높이 h를 갖게 하기 위해서는 m은 적어도 (N+1)1/h이어야 한다.
|
|
2.3 Binary Search Tree와의 비교
l m-one tree는 높이가 낮고 폭이 넓다. 한 단계씩 탐색과정을 진행할 때마다 Node의 대략 1/m로 줄어든다.
l
Binary Search Tree는 높이가 높고 폭이 좁다. 한 단계가 진행될 때마다 Node의 개수가 1/2로 줄어든다.
|
그림2. 3-one Search Tree와 Binary search tree의 비교 |
2.4 결론
l m-one tree의 성능을 향상시키기 위해서는 m을 크게 해야 하며 tree를 균형에 가깝도록 해야 한다.
l 균형에 가깝도록 tree의 형태를 만드는 것은 Tree를 처리하기 용이하게 하고 성능의 향상시킬 수 있다. 이런 형태의 tree를 B-Tree라 한다.
3. B-tree
3.1 정의
l 차수 m의 B-tree는 다음의 성질을 갖는다.
1) tree에 있는 각 Node는 최대 m개, 최소 (m/2)개의 종속 tree를 가져야 한다.
ð 이 조건에 의해 tree의 각 Node가 적어도 반 이상은 key값으로 채워져 있도록 한다. 따라서 종속 tree가 없는 Node가 발생하지 않고 key값이 가능한 효율적으로 종속 tree에 분배될 수 있도록 한다.
2) root Node는 최소한 두 개의 종속 tree를 가져야 한다. (단 tree가 root 만 있을 경우 종속 tree는 없다.)
ð 이 조건에 의해 tree가 처음부터 분기하도록 한다.
3) 모든 leaf Node는 같은 level에 있어야 한다. (즉, 모든 leaf Node는 root로부터 같은 거리에 있어야 한다.)
ð 모든 leaf Node가 root로부터 같은 거리에 있도록 하므로 tree가 거의 균형되게 하여 어느 leaf Node를 탐색하든 처리횟수가 같도록 한다.
4) Node의 key값의 개수는 종속 Tree의 개수보다 하나 적으며 최소 (m/2)-1개, 최대 m-1개이다.
정리)
B-tree는 차수 m을 갖는 empty 이거나 empty가 아닐 경우 height >= 1 이며 다음 조건을 만족하는 m-way search tree이다.
l root는 최소한 두 개의 children을 가진다.
l root node와 left node를 제외한 모든 node는 적어도 m/2개의 children을 갖는다.
l 모든 leaf node는 같은 level에 있다.
3.2 m의 선택
l disc에의 접근횟수를 감소시키기 위해서는 높은 차수의 B-tree를 사용하는 것이 바람직하다.
l 하지만 하나의 level만을 가지는 B-tree (m = N+1)의 경우 memory에 모든 key 값을 가져야 하므로 비효율적이다.
|
|
l 따라서 전체 탐색 시간을 줄일 수 있는 m을 선택하여야 한다.
l 최대 탐색 시간을 구하는 공식
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.3 B-tree의 연산
3.3.1 key 값의 순차적 처리
B-tree는 각 node를 중위순회(inorder) 하여 key 값을 순차처리 할 수 있다. 하지만 각 node는 여러 개의 key 값이 있기 때문에 각각의 node를 여러 번 방문하게 된다. 따라서 순차처리에서는 좋은 성능을 나타내지 못한다.
B-tree의 변형 구조에서는 좋은 성능을 기대할 수 있다.
|
|
3.3.2 Insertion
l Insertion/Deletion 연산 후에도 B-tree는 B-tree의 성질을 보존해야 하며 균형을 이루어야 한다. => 균형 algorithm 필요
l 규칙
Ø key 값은 항상 leaf node에서만 삽입된다.
Ø 새로운 key 값이 삽입된 node의 현재 key 값의 개수에 따라
ð 해당 node가 가득 차지 않았을 때 : 단순히 삽입
ð 해당 node가 가득 찼을 때 : 분열하여 중간 key 값을 부모 node로 보내고 나머지 key 값들을 둘로 나누어 각각 분열된 두 node로 옮긴다.
l 특징
Ø leaf node에서 삽입되고 root에서 자란다.
Ø 한 node가 분열되면 반만 채워진 두 개의 node가 생기므로 그 이후의 삽입은 분열 없이도 수행될 가능성이 높다. 즉, 한 번의 분열에 의해 여러 번의 단순 삽입이 가능해진다.
Ø 부모 node로 올라가는 key 값은 중간 값이므로 어떤 순서로 삽입하든 관계없이 tree 의 균형을 개선시킬 가능성이 많다.
|
그림5. B-tree 에서의 삽입과정 |
3.3.3 Deletion
l Deletion 연산은 항상 leaf node에서 이루어진다.
l Delete하려는 key 값이 leaf가 아닌 node가 아닌 node가 있다면 후행 key 값과 자리를 바꾸어 leaf node로 옮긴 후 삭제한다.
l 연산 결과 최소한의 key 값 ((m-2)-1)을 갖지 못한다면 재배치(redistribution)나 합병(merge, concatenation)하여 key 값의 개수를 조정한다.
|
|
3.3.3.1 재배치(redistribution)
Ø 해당 node의 left 또는 right node에 최소 key 값보다 많은 key 값을 갖고 있을 때 사용한다.
Ø 선택된 형제 node로부터 부모 node를 경유하여 key 값을 해당 node로 이동한다.
Ø 하나 이상의 key 값을 이동시켜서 (부모 node와 형제 node, 해당 node의 key 값 중 중간 값을 부모 node로 보내고 나머지를 2개로 나누어 할당한다.) key 값의 분포를 균형 있게 유지하여 tree 의 성능을 개선할 수 있다.
Ø Tree 구조의 변경은 없다.
3.3.3.2 합병 (merge, concatenation)
Ø 재배치가 불가능한 경우 사용
Ø insertion 시 분열의 반대 과정
Ø 부모 node와 형제 node의 key 값과 해당 node의 key 값을 하나의 node로 합병
Ø 합병당한 두 node중 하나를 새로 만들어진 node로 대치하고 나머지 한 node는 제거 한다.
Ø 최악의 경우 root node까지도 변경될 수 있다.
Ø Tree의 구조가 변경된다.
4. B*-tree
4.1 정의
B-tree의 문제점을 보완하기 위해 B-tree를 변형한 구조. 즉, B-tree에서는 제한 조건을 유지하기 위해 삽입과정에서 분열과 삭제과정에서 합병 등의 보조연산이 필요하다. B*-tree에서는 이런 보조연산을 감소시키려 헸다.
4.2 조건
l 각 node는 2/3가량 채워지면 된다. (B-tree는 1/2 이상)
l B*-tree는 node의 분열을 줄여서 보조연산을 줄이려고 한다. 따라서 node가 가득차면 분열하는 대신 이웃한 형제 node로 재배치를 한다.
l 한 node가 가득차고 인접 node까지 모두 가득찰 때까지 분열을 지연한다.
4.3 Insertion
l B-tree에서와 같은 방법으로 삽입을 한다.
l node가 가득차면 이웃한 형제 node를 살펴보아 빈자리가 있으면 정렬하여 재배치한다.
l 그림에서 관련된 전체 key 값은 7개이고 부모 node에 들어갈 한 개를 제외하면 6개가 되고 이 6개의 key값이 두 개의 node로 분할 되므로 6/2=3개씩 node에 분산된다. 그리고 부모 node에는 중간 값이 올라간다.
l 인접 node에도 overflow가 일어나서 더 이상 빈자리가 없을 경우 가득찬 두 node를 분열하여 2/3정도 찬 3개의 node로 만든다.
4.4 Deletion
B-tree와 똑같이 삭제 후 key 값의 개수가 모자라면 이웃한 형제 node로부터 재배치하고 재배치도 할 수 없는 경우 합병한다. 합병할 때는 세 개의 node를 두개의 node로 합병한다.
5. B+-tree
5.1 정의 : B-tree의 변형 구조로 index 부분과 leaf node로 구성된 순차 data 부분으로 이루어진다.
index 부분의 key 값은 leaf에 있는 key 값을 직접 찾아 가는데 사용하고 모든 key 값은 leaf에 나열된다. 즉, index 부분의 key 값도 leaf node에 다시 한 번 나열된다.
leaf node는 순차적으로 linked list를 구성하고 있어서 순차적 처리가 가능하다.
5.2 Insertion
l B-tree와 거의 동일하게 이루어진다.
l Node의 분열이 일어나면 중간 key 값이 부모 node로 올라갈 뿐 아니라 새로 분열된 node에도 포함되어야 한다.
l 새 node는 leaf node끼리의 linked list에도 삽입되어야 한다.
|
그림7. B+-tree 에서의 삽입과정 |
5.3 Deletion
l 재배치와 합병이 필요하지 않을 때는 leaf node에서만 삭제된다.
l Index 부분은 다른 key 값을 찾는데 사용될 수 있기 때문에 leaf node의 값이 삭제되어도 삭제하지 않는다.
l 재배치할 경우 index 부분의 node의 key 값은 변하지만 tree 구조는 변하지 않는다.
l 합병을 할 경우 index 부분에서도 key 값을 삭제한다.
6. 트라이 (Trie)
6.1 정의
하나의 key 값의 일부분만을 사용하여 분기하는 tree 구조이다. 보통 하나의 node는 m개의 pointer로만 구성된 1차원 배열이며 배열의 각 원소의 주소는 그 주소에 대응하는 숫자를 나타낸다.
예를 들어 key 값이 숫자로 구성된다면 이는 곧 10-one tree이다. 마찬가지로 key 값이 영문자로만 구성된다면 각 node는 26개의 key 값을 갖는 26-one tree가 된다.
Trie의 높이는 key 값의 길이에 의해 결정된다. link가 없는 node의 key 값은 0으로 나타내며 pointer가 모두 0인 node (종속 tree가 없는 node)는 나타내지 않음으로써 높이를 낮추고 기억공간을 절약할 수 있다.
6.2 성능
탐색시 B+-tree와 같이 leaf node까지 가야만 key 값을 찾을 수 있다. 하지만 찾는 key 값이 없을 경우 어느 level에서든지 끝낼 수 있다. 따라서 key 값이 없는 경우의 탐색 효율이 좋다.
6.3 Insertion/Deletion
l 새로운 key 값이 삽입이나 삭제될 leaf node를 찾기 위해서는 특정 key 값을 직접 탐색하여야 한다.
l 삽입시 새로운 node가 들어갈 leaf node가 없는 경우 index 부분에도 node를 삽입해야 한다.
l 위치가 결정되면 해당 위치의 0을 고쳐 key 값이 존재한다는 것을 나타내주거나 key 값의 Record 주소를 저장해야 한다.
l 삭제 시에는 해당 위치의 Pointer를 0으로 만들어 연결을 끊는다.
l Trie에서는 삽입이나 삭제시 node의 분열이나 합병이 없다.
6.4 Trie의 변형
기본 trie를 변형하여 효과적으로 사용할 수 있다.
6.4.1 가변길이의 key field 수용
예를 들어 영문자로만 구성된 이름을 key 값으로 사용하며 최대 key 값은 30로 구성될 때 높이 30인 26-one trie가 필요하다.
만약 key 값의 대부분이 8문자 이내라면 각 node에 27개의 원소를 가지도록 node를 구성하고 마지막 원소는 특수문자 (예를 들면 '$'와 같은)를 사용하여 이름이 끝난다는 표시를 나타내게 한다. 그리고 trie를 8 level로 구성하여 8자 이상인 이름은 이름의 나머지를 가지고 있는 다른 장소 (예를 들면 Binary Search Tree)를 가리키도록 하여 이름의 나머지를 찾도록 한다.
6.4.2 기억 장소 감소
예를 들어 영문자를 사용하는 key 값에서 모든 알파벳 문자를 나타내지 않고 실제 사용하는 알파벳만을 나타내도록 하면 모든 node가 26개의 key 값을 가질 필요가 없으므로 기억장소를 절약할 수 있다.
