B+ Tree (B+ 트리)

개념
모든 레코드들이 트리의 최하위 레벨에 정렬되어 있고 트리 내부 블록에는 키들만 저장됨.
파일시스템 같은 블록기반 스토리지에서 저장데이터의 효율적인 검색에 유용함.

알고리즘

검색

Function: search (k)  return tree_search (k, root);   Function: tree_search (k, node)  if node is a leaf then  return node;  switch k do  case k < k_0  return tree_search(k, p_0);  case k_i ≤ k < k_{i+1}  return tree_search(k, p_i);  case k_d ≤ k  return tree_search(k, p_d);

삽입
1. 새 레코드를 삽입하기위한 검색을 수행
2. 노드에 남은 공간이 있으면 레코드 삽입.
3. 노드가 다 차있으면 분할실행.
    3.1 새 리프를 할당하고 노드에 있던 원소의 절반을 새 노드로 이동시킴.
    3.2 새 리프에 가장 작은 키를 삽입하고 부모노드에서 참조시킴.
    3.3 부모노드역시 다 차있으면 부모노드도 분할함.
         3.3.1 부모노드에 중간 키를 추가함.
    3.4 부모노드가 분할되지 않을때까지 반복함.
4. 루트가 분할되면 키하나와 포인터 2개를 가진 새로운 루트를 만듬

삭제
1. 루트에서 시작해서 해당 원소가 있는 리프노드를 찹음.
2. 해당 원소를 삭제
    2.1 리프가 절반이상 차있으면 종료.
    2.2 리프의 원소가 절반보다 작으면 다음과정 수행
         2.2.1 사촌노드들에서 원소를 가져와서 재분배 수행.
         2.2.2 재분배가 실패하면 사촌노드와 병합함.
3. 병합이 발생하면 해당 리프노드를 가르키는 부모노드의 원소를 삭제함.


참고
1. http://en.wikipedia.org/wiki/B%2B_tree
2. http://ko.wikipedia.org/wiki/B%2B_%ED%8A%B8%EB%A6%AC