[자료구조] - B Tree & B+ Tree

1. B Tree

• 데이터베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종이다.

• 이진 트리를 확장해서, 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것이 B-Tree

2. 규칙

• 노드의 자료수가 N이면, 자식 수는 N+1이어야 함
• 각 노드의 자료는 정렬된 상태여야함
• 루트 노드는 적어도 2개 이상의 자식을 가져야함
• 루트 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야함
• 외부 노드로 가는 경로의 길이는 모두 같음.
• 입력 자료는 중복 될 수 없음

3. B+ Tree

• 데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드(not Leaf)가 추가로 있음
  (기존의 B-Tree와 데이터의 연결리스트로 구현된 색인구조)

• B-Tree의 변형 구조로, index 부분과 leaf 노드로 구성된 순차 데이터 부분으로 이루어진다. 인덱스 부분의 key 값은 leaf에 있는 key 값을 직접 찾아가는데 사용함.

4. 장점

• 블럭 사이즈를 더 많이 이용할 수 있음 (key 값에 대한 하드디스크 액세스 주소가 없기 때문)

• leaf 노드끼리 연결 리스트로 연결되어 있어서 범위 탐색에 매우 유리함

5. 단점

• B-tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+tree는 무조건 leaf 노드까지 내려가봐야 함

6. B-Tree & B+ Tree

• B-tree는 각 노드에 데이터가 저장됨

• B+tree는 index 노드와 leaf 노드로 분리되어 저장됨
  (또한, leaf 노드는 서로 연결되어 있어서 임의접근이나 순차접근 모두 성능이 우수함)

• B-tree는 각 노드에서 key와 data 모두 들어갈 수 있고, data는 disk block으로 포인터가 될 수 있음

• B+tree는 각 노드에서 key만 들어감. 따라서 data는 모두 leaf 노드에만 존재

• B+tree는 add와 delete가 모두 leaf 노드에서만 이루어짐