[파일구조] B tree 와 B+ tree

B-Tree

---

검색을 위한 자료구조 중에서 이진 트리는 비록 하나의 부모가 두 개의 자식밖에 가지질 못하고 자칫 균형이 맞지 않으면 검색 효율이 선형검색 급으로 떨어지지만 잠재력이 가장 크다. 그렇지만 이진 트리는 구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN)의 성능을 보이는 장점이 있어서 이를 바탕으로 개선하고자 하는 노력이 많이 있어 왔다.

그 중에서도 B-Tree는 이진트리를 확장해서 더 많은 수의 자식을 가질 수 있게 일반화하였다. B-트리는 자식 수에 대한 일반화를 하면서 하나의 레벨에 더 많이 저장되는 것 뿐만 아니라 트리의 균형을 자동으로 맞추는 로직까지 갖추었다. 게다가 이 균형 로직은 단순하면서도 효율적이다. 그래서 B-트리는 레벨로만 따지면 완전히 균형을 맞춘 트리이다.

대량의 데이터를 처리해야 하는 검색 구조인 경우 하나의 노드에 많은 데이터를 가질 수 있다는 점은 큰 장점이다.

대량의 데이터는 메모리 보다는 하드디스크 혹은 SSD에 저장되어야 하는데 이들 외부 기억 장치들은 블럭 단위로 입출력을 하기 때문이다.

예를 들어 한 블럭이 1024 바이트라면 2바이트를 읽으나 1024 바이트를 읽으나 입출력에 대한 비용은 동일하다. 그렇다면 하나의 노드를 1024바이트가 되도록 조절한다면 입출력 면에서 매우 효율적인 구성이 된다. 이런 장점으로 실제 B-Tree는 많은 데이터베이스 시스템의 인덱스 저장 방법으로 애용되고 있다.

B-트리란 하나의 노드에 여러자료가 배치되는 트리 구조이다. 한 노드에 M개의 자료가 배치되면 M차 B-Tree라고 한다.

5차 B-트리 인 경우 자식노드가 최대 5개인 것을 의미한다. B-트리는 스스로 균형을 맞추는 트리이다 .그래서 최악의 경우에도 O(logN)의 검색 성능을 보인다. 또한 B-트리는 하나의 노드에 많은 수의 데이터를 저장할 수 있다. 

규칙

• 노드의 자료수가 N이라면 자식의 수는 N+1이어야 한다. 
• 각 노드의 자료는 정렬된 상태여야 한다.
• 노드의 자료Dk의 왼쪽 서브트리는 Dk보다 작은 값들이고 오른쪽 서브트리는 Dk보다 큰 값들이어야 한다.
• Root 노드는 적어도 2개이상의 자식을 가져야 한다.
• Root 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다.
• 외부 노드로 가는 경로의 길이는 모두 같다. - 외부노드는 모두 같은 레벨에 있다
• 입력자료는 중복될 수 없다. 

B-tree 삽입/삭제에 대한 설명  http://potatoggg.tistory.com/174

코드  http://ddmix.blogspot.kr/2015/01/cppalgo-18-b-tree-search.html

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 값을 삭제한다.

http://egloos.zum.com/sweeper/v/899699

예시)

b트리와 달리 트리의 최하위 레벨의 리프노드에만 데이터 들이 정렬되어있음. 
나머지 노드들은 키값만 가지고 있다.
파일시스템 같은 블록기반 스토리지에서 저장데이터의 효율적인 검색에 유용함

58
1234/567/89 10

이와같이 인덱스에 사용되던 키값마저 리프노드에 중복되어있다.
또한 1->2->3->4->5->.,...->10순으로 각 리프로드가 링크되어 linked list를 구성하고 있기 때문에
데이터의 순차적 처리가 가능하다.

출처: http://lssang.tistory.com/entry/알고리즘-B트리-B트리 [쩡자의 개발노트]

B-tree 와 B+tree

 B-tree와 각 노드에 데이터가 저장이 되지만 B+tree의 경우엔 인덱스노드와 리프노드가 분리되어서 존재한다. 그리고, 리프노드는 서로 연결되어 있어서 임의접근과 순차접근모드 성능이 우수하다. 

공통점

1. 모든 leaf의 depth가 같다

2. 각 node에는 k/2 ~ k 개의 item이 들어있어야 한다.

3. search가 비슷하다.

4. add시 overflow가 발생하면 split 한다

5. delete 시 underflow가 발생하면 redistribution하거나 merge 한다.

차이점

1. B-tree의 각 노드에서는 key 뿐만 아니라 data도 들어갈 수 있다. 여기서 data는 disk block으로의 포인터가 될 수 있다.
  B+tree는 각 node에서는 key만 들어가야 한다. 그러므로 B+tree에서는 data는 오직 leaf에만 존재한다.

2. B+tree는 B-tree와는 달리 add, delete가 leaf에서만 이루어진다.

3. B+ tree는 leaf node 끼리 linked list로 연결되어 있다.

B+tree의 장점

- 블럭사이즈(노드사이즈) 를 더 많이 이용할수잇다 ( 키값에 대한 harddisk 엑세스 주소가 없기 때문에 )

- leaf node 끼리 linked list로 연결되어있어서 시퀀셜한 레인지 탐색에 매우 유리하다 

B + Tree 의 단점

- B Tree의 경우 best case에는 루트에서 끝날수 있지만, B+ Tree의 경우 무조껀 leaf노드까지 가야한다.

출처: http://hoonb.tistory.com/6 [HOONB]