B-Tree

<Tree의 검색 효율>
- 트리구조는 일종의 색인구조로서 데이터의 검색(인덱스:Index)이 주요 목적

*색인구조 : 문서에서 키워드를 찾아보기 쉽도록 정렬/나열한 목록 
  일반적으로 책 뒷편에 색인, 인덱스, 찾아보기와 같은 이름으로 정돈된 목록을 의미

- 신속한 데이터의 검색은 시스템의 성능에 결정적 영향
- 검색 속도는 원하는 데이터를 찾을 때까지의 경로 상 노드 숫자에 비례
- 노드의 크기에 따라 검색 속도가 변화
- ex) 실제 상황에서의 AVL 트리의 높이는 아래와 같다(n은 입력된 데이터의 개수)
  O(log2n) = log2(n+1)+0.25

- 따라서 데이터의 개수가 약 1000개라면 트리의 높이는 10이되고,
  데이터를 검색할 때 최악의 경우라도 10개의 노드를 거치면 찾을 수 있음을 의미한다

- 실제로 운영되는 트리구조는 대량의 데이터를 처리한다
  예를 들어 데이터의 개수가 1000만개라면 이진트리의 높이는 약 24가 된다

- 데이터베이스에서 처리하는 방대한 데이터는 메인 메모리가 아닌 보조기억장치에 보관처리하게되고
  24번의 보조기억장치에 대한 데이터의 접근이 필요하게 된다

- 너무 많은 기억장치에 대한 접근은 효율(처리시간)저하 유발

- 효율적 트리구조는 트리의 높이가 최대한 낮아야 한다

- 최대한 균형상태를 유지해야하며 노드의 용량(데이터를 저장하는 공간)이 데이터 이동단위에 비례

- 데이터베이스와 같은 시스템의 검색구조로 사용되기에 이진트리는 부적절
  - 이진트리는 트리의 용량이 너무 적다

- 대량의 정보처리에 적절한 B-tree와 같은 검색구조가 생성
*이진트리의 차수(자식의 개수)는 최대2
  즉, 하나의 노드에 1개의 데이터가 저장




<B-Tree>
- Order(차수 : 자식노드의 최대개수) m의 B-tree는 아래와 같은 특성을 갖는다
  - 루트노드는 말단 노드이거나 자식을 2개에서 m개 갖는다
  - 루트노드를 제외한 모든 비말단 노드의 자식 수 C :
  [m/2] <= c <= m
  - 모든 말단노드는 동일한 깊이에 존재한다
  - 모든 데이터는 말단노드에 저장된다

- 말단 노드 구조, 비 말단 노드 구조
  - 말단 노드는 실제의 데이터 값 또는 키 값을 포함한 레코드의 주소 값을 간직할 수 있다

- 말단 노드의 데이터 값의 개수 C : [m/2] <= c <= m
  - m은 차수이며 차수는 자식노드 최대 갯수이다

- 차수가 3인 B-Tree 사용 -> 말단노드도 3개의 데이터가 저장(즉, m=3)
  - 최초에는 말단노드 1개만 존재, 만약 말단노드에는 4개의 데이터가 저장되면
    노드가 용량초과로 분할(split)된다 -> overflow(포인터 공간이 부족)

- 분할된 색인 노드를 상위 루트 노드에 연결하기 위한 포인터 공간이 부족(overflow)하므로 루트 노드 역시 분할되어야 한다
- 루트 노드 분할 역시 다른 색인 노드의 분할과 동일한 방식으로 이루어진다

- 노드의 분할(split)
  - B-Tree는 노드 분할을 수행함 크기가 성장한다. B-Tree의 차수(order)가 m이라고 하자
  - 하나의 키 값이 B-tree에 삽입될 때 만일 삽입될 노드에 이미 m개의 키 값이 존재하는 경우, 노드가 분할된다
  - 노드는 두 개로 분할해야한다. 분할될 노드의 m+1개의 키는 아래와 같이 두 개의 노드로 분배된다
    - [(m+1)/2]-자릿수 올림 , [(m+1)/2]-자릿수 내림
    - 만약 m=4라면 한 쪽 노드는 데이터를 2개, 3개로 분할
   
- 오른쪽 서브트리의 최소값이 '지시자 값'이다

- 트리의 레벨이 높아지면 말단노드에 저장되는 데이터의 양이 많아진다 -> 트리가 성장