자료구조 - BTree

B-Tree

---

B-tree

• B의 의미는 balance를 의미한다.

• 군형잡힌 다진검색트리로 다음의 성질을 만족한다. (다진검색트리란 자식을 여러개 갖는 트리를 말한다.)

  1. 루트 제외 모든 노드는 최소 k/2 ~ k개의 키를 갖는다.

  2. 모든 리프노드는 같은 깊이를 갖는다.

• 디스크에 저장하는 cost를 최소화하여 데이터베이스에서 주로 사용된다. 최악의 경우 디스크 접근 횟수를 줄일 수 있다.

 

B-tree의 삽입

• 삽입 후 오퍼플로우가 발생하면(키의 수가 k보다 많으면) 형제 노드(양 옆의 노드) 중 여유가 있는 노드가 있으면 남는 키를 형제 노드에게 삽입해 준다.
• 없으면 오버플로가 발생한 레코드를 둘로 분할하고 가운데 키를 부모 노드로 넘긴다.

 

B-tree의 삭제

• 삭제 후 언더플로우가 발생하면(키의 수가 k/2보다 작으면) 형제 노드중 키를 하나 내놓을 수 있는 여유가 있는노드가 있으면 형제 노드에게 키를 전달받는다. 
• 없으면 레코드를 형제 노드와 합병한다.

 

reference