출처: http://sweeper.egloos.com/899699
1. B* Tree
1. 정의
B-Tree의 각 노드는 디스크의 블록과 같기 때문에 노드 하나를 접근하는 것은 디스크를 한번 더 접근하는 것을 의미한다. 그러므로 보다 적은 수의 노드를 생성하는 것이 색인구조의 성능을 높일 수 있다. 생성되는 노드의 수를 줄이기 위해 B-Tree의 변형으로 B* 트리가 나오게 되었다.
B-Tree는 특성을 유지하기 위해 삽입과정에서의 분열과 삭제 과정에서의 합병 등의 보조 연산이 필요하다. B* Tree에서는 이런 보조 연산을 가급적 지연시켜 회수를 감소시키려 헸다.
2. 조건
1) Root 노드를 제외한 모든 노드는 2/3 이상 채워져야 된다. (B-Tree는 1/2 이상)
2) B* Tree는 노드의 분열을 줄여서 보조 연산을 줄이려고 한다. 따라서 노드가 가득차면 분열하는 대신 이웃한 형제 노드로 재배치를 한다.
---> 재배치 작업은 부모노드+해당노드+형제노드의 key들을 나열한 뒤, 중간 key 값을 부모 노드로 보내고 남은 key들을 반분하여 해당노드와 형제노드에 배치하는 행동이다. 중요한 것으므로 이해 필요;
3) 한 노드가 가득차고 인접 노드까지 모두 가득찰 때까지 분열을 지연한다.
이러한 노력으로 B* 트리의 평균 저장공간 사용률은 81%에 달한다. (Leung, 1984)
3. 삽입
1) B-Tree에서와 같은 방법으로 삽입을 한다.
2) 노드가 가득차면 이웃한 형제 노드를 살펴 빈 자리가 있으면 정렬하여 재배치한다.
3) 인접 노드에도 key 넘침 현상(overflow)이 일어나서 더 이상 빈 자리가 없을 경우, 가득찬 두 노드를 분열하여 2/3 정도 채워진 3개의 노드로 만든다. 이 과정에서 재배치 동작은 2번 발생한다. (가득찬 두 노드를 분열하여 3개의 노드로 만들 때 첫번째 노드와 두번째 노드간의 재배치 그리고 두번째 노드와 세번째 노드간의 재배치)
4. 삭제
B-Tree와 똑같이 삭제 후 key 값의 개수가 모자라면 이웃한 형제 노드로부터 재배치하고 재배치도 할 수 없는 경우 합병한다. 합병할 때는 세 개의 노드를 두 개의 노드로 합병한다.
2. B+ Tree
B-트리는 특성상 순회 작업이 상당히 난감하다. B+ 트리는 색인구조에서 순차접근에 대한 문제의 해결책으로 제시되었다. (Wedekind, 1974) B-트리에서는 특정 key 값이 하나의 노드에서만 존재할 수 있지만 B+ 트리에서는 leaf 노드와 leaf의 부모 노드에서 공존할 수 있다. B+ 트리의 비단말 노드(not leaf)들은 데이터의 빠른 접근을 위한 인덱스 역할만 하기 때문이다. (index set 이라 불린다) 그리고 leaf 노드들은 연결 리스트 형태로 서로 연결되어 있고 이를 순차집합(sequence set)이라고 하며 오름차순으로 정렬이 되어 있다. 고로 B+ 트리는 (기존의 B-트리 + 데이터의 연결 리스트)로 구현된 색인구조라고 할 수 있다.
1. 정리 : B-트리의 변형 구조로 index 부분과 leaf 노드로 구성된 순차 data 부분으로 이루어진다. Index 부분의 key 값은 leaf에 있는 key 값을 직접 찾아 가는데 사용하고 모든 key 값은 leaf 노드에 나열된다. 즉, index 부분의 key 값도 leaf 노드에 다시 한 번 나열된다. Leaf 노드는 순차적으로 linked list를 구성하고 있어서 순차적 처리가 가능하다.
2. 삽입
1) B-tree와 거의 동일하게 이루어진다.
2) 노드의 분열이 일어나면 중간 key 값이 부모 노드로 올라갈 뿐 아니라 새로 분열된 노드에도 포함되어야 한다.
3) 새 노드는 leaf 노드끼리의 linked list에도 삽입되어야 한다.
3. 삭제
1) 재배치와 합병이 필요하지 않을 때는 leaf 노드에서만 삭제된다.
2) Index 부분은 다른 key 값을 찾는데 사용될 수 있기 때문에 leaf node의 값이 삭제되어도 삭제하지 않는다.
3) 재배치할 경우 index 부분의 node의 key 값은 변하지만 tree 구조는 변하지 않는다.
4) 합병을 할 경우 index 부분에서도 key 값을 삭제한다.
B+ 트리에 대해 구글링으로 겟한 문서를 첨부한다
1. B* Tree
1. 정의
B-Tree의 각 노드는 디스크의 블록과 같기 때문에 노드 하나를 접근하는 것은 디스크를 한번 더 접근하는 것을 의미한다. 그러므로 보다 적은 수의 노드를 생성하는 것이 색인구조의 성능을 높일 수 있다. 생성되는 노드의 수를 줄이기 위해 B-Tree의 변형으로 B* 트리가 나오게 되었다.
B-Tree는 특성을 유지하기 위해 삽입과정에서의 분열과 삭제 과정에서의 합병 등의 보조 연산이 필요하다. B* Tree에서는 이런 보조 연산을 가급적 지연시켜 회수를 감소시키려 헸다.
2. 조건
1) Root 노드를 제외한 모든 노드는 2/3 이상 채워져야 된다. (B-Tree는 1/2 이상)
2) B* Tree는 노드의 분열을 줄여서 보조 연산을 줄이려고 한다. 따라서 노드가 가득차면 분열하는 대신 이웃한 형제 노드로 재배치를 한다.
---> 재배치 작업은 부모노드+해당노드+형제노드의 key들을 나열한 뒤, 중간 key 값을 부모 노드로 보내고 남은 key들을 반분하여 해당노드와 형제노드에 배치하는 행동이다. 중요한 것으므로 이해 필요;
3) 한 노드가 가득차고 인접 노드까지 모두 가득찰 때까지 분열을 지연한다.
이러한 노력으로 B* 트리의 평균 저장공간 사용률은 81%에 달한다. (Leung, 1984)
3. 삽입
1) B-Tree에서와 같은 방법으로 삽입을 한다.
2) 노드가 가득차면 이웃한 형제 노드를 살펴 빈 자리가 있으면 정렬하여 재배치한다.
3) 인접 노드에도 key 넘침 현상(overflow)이 일어나서 더 이상 빈 자리가 없을 경우, 가득찬 두 노드를 분열하여 2/3 정도 채워진 3개의 노드로 만든다. 이 과정에서 재배치 동작은 2번 발생한다. (가득찬 두 노드를 분열하여 3개의 노드로 만들 때 첫번째 노드와 두번째 노드간의 재배치 그리고 두번째 노드와 세번째 노드간의 재배치)
4. 삭제
B-Tree와 똑같이 삭제 후 key 값의 개수가 모자라면 이웃한 형제 노드로부터 재배치하고 재배치도 할 수 없는 경우 합병한다. 합병할 때는 세 개의 노드를 두 개의 노드로 합병한다.
2. B+ Tree
B-트리는 특성상 순회 작업이 상당히 난감하다. B+ 트리는 색인구조에서 순차접근에 대한 문제의 해결책으로 제시되었다. (Wedekind, 1974) B-트리에서는 특정 key 값이 하나의 노드에서만 존재할 수 있지만 B+ 트리에서는 leaf 노드와 leaf의 부모 노드에서 공존할 수 있다. B+ 트리의 비단말 노드(not leaf)들은 데이터의 빠른 접근을 위한 인덱스 역할만 하기 때문이다. (index set 이라 불린다) 그리고 leaf 노드들은 연결 리스트 형태로 서로 연결되어 있고 이를 순차집합(sequence set)이라고 하며 오름차순으로 정렬이 되어 있다. 고로 B+ 트리는 (기존의 B-트리 + 데이터의 연결 리스트)로 구현된 색인구조라고 할 수 있다.
1. 정리 : B-트리의 변형 구조로 index 부분과 leaf 노드로 구성된 순차 data 부분으로 이루어진다. Index 부분의 key 값은 leaf에 있는 key 값을 직접 찾아 가는데 사용하고 모든 key 값은 leaf 노드에 나열된다. 즉, index 부분의 key 값도 leaf 노드에 다시 한 번 나열된다. Leaf 노드는 순차적으로 linked list를 구성하고 있어서 순차적 처리가 가능하다.
2. 삽입
1) B-tree와 거의 동일하게 이루어진다.
2) 노드의 분열이 일어나면 중간 key 값이 부모 노드로 올라갈 뿐 아니라 새로 분열된 노드에도 포함되어야 한다.
3) 새 노드는 leaf 노드끼리의 linked list에도 삽입되어야 한다.
3. 삭제
1) 재배치와 합병이 필요하지 않을 때는 leaf 노드에서만 삭제된다.
2) Index 부분은 다른 key 값을 찾는데 사용될 수 있기 때문에 leaf node의 값이 삭제되어도 삭제하지 않는다.
3) 재배치할 경우 index 부분의 node의 key 값은 변하지만 tree 구조는 변하지 않는다.
4) 합병을 할 경우 index 부분에서도 key 값을 삭제한다.
B+ 트리에 대해 구글링으로 겟한 문서를 첨부한다
invalid-file
