B+ Tree

‘위키피디아(https://en.wikipedia.org/wiki/B%2B_tree)’를 참고하여 작성하였습니다.

B+ 트리

특징

• 각 노드는 레코드 또는 자식 노드를 가진다. internal node는 자식 노드만, 리프 노드는 레코드만을 가진다. 둘다 가지는 경우는 없다.
• b는 internal node의 용량을 측정하는 인자이며, 자식 노드의 최대 개수를 의미한다. 트리 전체에서 일정하다.
• internal node의 실제 자식 수 m : $b/2 <= m < b$ 이다.
• root 노드의 경우 최소 자식 수는 2이다.
• 노드의 레코드와 키는 모두 오름차순으로 정렬
• internal 노드들에는 각 자식 노드들을 가리키는 포인터들이 있다.
• 이 포인터들을 노드 내의 키들이 구분한다.
• 그래서 키의 수 $n = b - 1$
• 키를 보고 포인터를 선택해 해당 자식 포인트로 나아간다.
• 리프 노드들이 순차적인 링크드 리스트로 연결 되어있다.
• 그래서 순차탐색도 가능해 b- 트리보다 효율적이다.
• 블록 크기가 B 이고, 저장할 키의 크기가 k 인경우 효율적인 b = (B / k) -1 이다.
• 블록의 크기를 프로세서 캐시 라인의 크기로 설정하면 좋다.

알고리즘	복잡도
공간	$O(N)$
탐색	$O(logN)$
삽입	$O(logN)$
삭제	$O(logN)$

탐색

• 루트노드에서 탐색을 시작한다.
  1. 노드 내의 키들을 선형 검색하며 찾는 값과 비교해 원하는 자식 노드를 가리키는 포인터를 찾는다.
  2. 리프 노드 에 도착할때 까지 자식노드에서 1을 반복한다.

삽입

• 먼저삽입될 리프 노드 위치를 탐색을 통해 찾고 삽입한다.
• 리프노드 내 키의 개수가 용량을 초과하는 경우,
  1. 중앙 키를 기준으로 두 노드로 분리 후,
  2. 중앙 키를 부모 노드로 삽입한다.
  3. 만약 부모 노드도 용량을 초과하는 경우, 1과 2를 반복한다.

삭제

• 삭제할 리프 노드 위치 탐색 후 삭제한다.
• 리프노드 내의 키의 개수가 최소 용량보다 적어지는 경우,
  1. sibling 노드의 중앙 키를 기준으로 두 노드로 나누고,
  2. 키가 삭제된 리프 노드와 나뉜 노드 하나를 병합한다.
  3. 부모 키를 중앙키로 대체한다.
• 삭제 후 , 리프노드 내의 키의 개수가 최소 용량보다 적고, sibling 노드에 키의 개수가 용량의 과반을 넘지 않아 가져올 수 없는 경우,
  1. 키가 삭제된 리프 노드와 sibling 노드를 병합한다.
  2. 리프 노드 개수가 하나 줄었으므로 부모 노드의 키를 하나 제거한다.
  3. 부모 노드 내의 키의 개수가 최소 용량보다 적어지는 경우, 위를 반복한다.