2016/11/03 멀티미디어 시스템(차광호 교수님) B+Tree

트리 구조는 검색에 유용하다 왜냐하면 조건에 맞는 노드를 찾아갈 때 필요없는 것을 순식간에 자를 수 있기 때문이다.(잘라내기=pruning 이라고 한다)
이 때문에 구글, 네이버 등 검색 사이트들에서는 이러한 트리의 색인을 이용해 검색 알고리즘에 사용한다.

 b-tree는 balanced 트리로 다양한 변형이 존재한다. 그 중 b+ tree가 구조상 삽입,삭제가 쉽기 때문에 가장 많이 사용한다.
balanced 트리는 루트에서 leaves 노드들 까지의 깊이(길이)가 같은 트리를 말한다.

자료구조를 배울 때 많이 나오는 binary 트리는 최대 자식노드가 2개이기 때문에 트리의 깊이가 깊고 몸체가 얇다. 반면, b+tree는 자식노드가 100개 이상으로 굉장히 많아 트리의 깊이는 얕고 몸체가 두꺼운 형태를 갖는다.
트리들은 노드들간 포인터로 연결되는데, binary 트리는 memory용 자료구조로 memory는 접근시간이 빠르기 때문에 깊이가 깊더라도 빠르게 검색을 할 수 있다. 데이터베이스에서 자주 사용하는 b+트리는 보조기억장치 혹은 많은 사용자가 공유하기 때문에 자료 접근에 상대적으로 많은 시간이 걸린다. 그래서 트리의 깊이를 얕게 한 것이다.

b+트리에서 하나의 노드는 n개의 포인터와 n-1개의 키값으로 구성된다. 이 때 n을 fanout 혹은 blocking factor라고 부르며 하나의 b+트리에 n은 고정되어 있다.

루트가 아닌 비단말 노드의 자식노드 숫자 조건 : 단말노드의 value 숫자 조건

   데이터 밀도가 절반 이하로 떨어지지 않아야 한다는 의미로, 성능에 영향을 미치는 조건이다.

 b+tree의 leaf 노드 : 실제 데이터를 가르키는 포인터와 키값이 한 쌍

 b+tree의 nonleaf 노드 : 중간에 있는 키값보다 작은것이 위치한 노드를 가르키는 포인터 키값과 같거나 큰 노드를 가르키는 포인터들로 구성

 b+트리 예제

b+트리에서 n에 따른 children 숫자 조건, key value 숫자 조건을 보여주는 예제

 검색(query)은 트리 탐색과 같다. 빨간색 검색 경로의 길이에서 [n/2]는 최소 child 숫자 조건에서 나왔던 n/2와 관련이 있다.

 삽입,삭제의 알고리즘에서 balanced 트리 조건을 만족하기 위해 오버플로우-노드 분할 / 언더플로우-노드 병합이 필요하다고 얘기하고 있다.

삽입 알고리즘, 키값이 홀 수 개일 경우 분할 과정에서 알고리즘상 [n/2]라서 왼쪽이 오른쪽보다 1개 더 많이 가질 수도 있다.

 삽입 전-후 예제

 삭제 알고리즘

 삭제 예제1-삭제, 병합

 삭제 예제2-부모 루트까지 영향을 주는 병합

삭제 예제3-부모 루트까지 영향을 주는 병합