B-Tree

출처 : http://yatoyato.tistory.com/1013

B-Tree

Order(차수: 자식노드의 최대 개수) m의 B-tree는 아래와 같은 특성을 갖는다.

• 루트노드는 말단노드이거나 자식을 2개에서 m개 갖는다.
• 루트노드를 제외한 모든 비말단 노드의 자식 수:

• 모든 말단 노드는 동일한 깊이에 존재한다.
• 모든 데이터는 말단노드에 저장된다.
• 구조

• p1, p2, ..., pm: 자식노드의 포인터
• d1, d2, ..., dm-1:은 p2, ..., pm이 가리키는 부속트리의 최소값을 표현한다.
• 모든 노드에 대해 p1이 가리키는 부속트리의 모든 데이터 값은 p2가 가리키는 부속트리의 모든 값보다 작다.
• 말단노드는 실제의 데이터 값 또는 키 값을 포함한 레코드의 주소값을 간직할 수 있다.
• B-tree는 여러 변형된 형태가 존재하지만 대부분 기본적인 구조는 동일하다.
• 말단노드의 데이터 값의 개수 C는 다음과 같다.

• 아래 그림은 차수가 4인 B-tree의 예이다.

• B-tree의 삽입연산 과정을 예를 들어보자. 아래 예제에서는 차수가 3인 B-tree가 사용된다.

• 트리에 23을 삽입: 23은 말단 노드에 저장되고 B-tree의 구조는 변함이 없게 된다.

• 키값 20을 삽입: 노드의 분할(node split)이 이루어진다. 노드의 분할 후 2개의 말단노드에 키 값 4개(15, 18, 19, 20)을 균등히 분할하면 아래 그림과 같은 상태가 된다.
• 세번째 말단노드(19, 20)를 가리키는 포인터를 상위노드에 저장: 상위색인 노드의 분할이 이루어져야 한다.
• 하나의 색인 노드가 분할하면 2개의 색인노드, 각 색인 노드는 2개의 자식포인터를 갖는다.
• 이러한 노드분할은 루트노드까지 거슬러 올라가면서 진행되거나, 또는 2개의 자식노드만 갖는 노드를 중도에 만날 때까지 진행된다.

• 아래 그림은 색인노드가 분할한 뒤에 말단노드 2개씩을 자식포인터로서 갖도록 재구성한 결과
• 루트노드는 분할할 필요가 없다.

• 다음 그림은 45를 삽입하고 30을 삽입한 뒤의 상태를 보여준다.
• 45가 삽입된 후 말단노드 분할 후 상위노드의 구조에 변화가 없으나, 30을 삽입했을 때 말단노드의 분할과 상위노드의 분할이 일어난다.

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

• 아래 그림은 루트노드가 분할된 뒤의 B-tree의 구조를 보여준다.
• 이러한 방식은 B-tree의 높이가 증가되면서 많은 데이터를 저장할 수 있게 된다.
• 노드 분할은 루트노드까지 거슬러 올라가면서 계속되거나 중간에 하나의 키 값만을 가진 노드를 만나면 중단된다.

• B-tree삭제연산: 일반적인 검색/삭제연산과 동일
• 만일 삭제연산을 한 뒤, 말단노드에 하나의 키 값만이 남게되면, 다음 중 하나의 방법에 의해 재구성한다.
• 만일 이웃한 형제노드가 3개의 키 값을 가지고 있는 경우: 하나의 키 값을 형제노드에서 가져와 두 개의 말단노드가 2개씩의 키 값을 갖도록 구성
• 만일 이웃한 형제노드가 2개의 키 값 만을 가지고 있는 경우: 두 개의 말단노드를 하나로 합쳐 3개의 키 값을 갖는 하나의 말단노드로 만든다. 이 경우, 부모노드의 자식 수가 하나 감소하므로 부모노드를 재구성한다. 이와 같은 방식으로 루트노드까지 거슬러 올라가면서 재구성을 수행
• 만일 루트노드가 하나의 자식만 갖게 된다면 루트노드를 삭제하고 트리의 높이가 하나 낮아진다.
• 노드를 합쳐서 하나로 만드는 경우, 색인노드에 저장된 정보를 업데이트 해주어야 한다.
• B-tree는 노드분할을 수행하면 크기가 성장한다.
  B-tree의 차수order가 m이라고 하자.
• 하나의 키 값이 B-tree에 삽입될 때 만일 삽입될 노드에 이미 m개의 키 값이 존재하는 경우,
• 노드는 두 개로 분할해야 한다. 분할될 노드의 m+1개의 키는

개의 키로 두 개의 노드에 분배된다.

• B-tree의 깊이의 최대값은 아래와 같다.

• 경로 상에 있는 모든 노드에 대해서 어떤 가지를 택할 것인가를(이진 검색을 사용한다면) 결정하기 위해 O(log₂m)의 작업이 요구된다.
• 최악의 경우, 삽입/삭제연산에 있어 수행시간은

• 그러나 단순검색 연산은 O(log_mn)이 걸린다. 실험적으로 얻어진 최상의 성능을 갖는 m값은 3 또는 4가 된다.
• m값이 커지면 삽입/삭제연산 시간이 증가된다. 만일 메인 메모리상에서 처리속도만 고려한다면 차수가 높은 B-tree는 성능이 좋지 못하다.
• 그러나 B-tree의 실제 응용분야는 데이터베이스 시스템과 같은 대량의 데이터를 처리
• 메인메모리 기반의 정보처리를 하지 않는다.
• 차수 m의 B-tree를 사용하는 경우 디스크 엑세스 횟수는 O(log_mn)이 걸린다. 물론 각 노드에서 어떤 하위 자식노드를 택해야 하는지를 결정하는 연산은 O(log₂m)이 걸리지만 한 블록의 메모리를 읽어들이는 시간에 비하면 상대적으로 작은 것으로 중요한 고려사항이 되지 못한다.
• 비록 업데이트가 요구되고 O(m)의 연산시간이 각 노드에 대해 요구된다고 해도 이 시간 역시 중요한 의미를 갖지 못한다. 따라서 하나의 디스크 블록을 하나의 색인노드로 채울 수 있을 정도의 m값을 선택해야 한다.
• 실제 응용에서 m값의 범위는 32<=m<=256정도가 된다.
• 말단노드의 용량역시 하나의 말단노드가 하나의 디스크 블록을 채울 수 있는 크기가 되도록 결정한다.
• 실제 응용에서 B-tree의 깊이는 2~3정도 밖에 되지 않는다.
• 또한 루트노드는 항상 메인 메모리에 상주시키므로 처리속도를 더욱 줄일 수 있다.