위의 이미지는 위키피디아 B+ tree의 정보에 담겨있는 이미지를 가져왔음을 밝힘.

데이터베이스에서 B+ 트리의 장점은 굉장히 많다. 또한 단점도 있다.

우선 장점으로는 딱 하나의 결과를 원하는 Point 질의와 특정 범위의 다수의 결과를 원하는 Range 질의를 둘 다 잘 처리할 수 있다는 장점이 있다. 그리고 단점으로는 삽입과 삭제의 과정에서 유지하는데 들어가는 비용이 적지 않다는 것이다.

위의 이미지는 B+ 트리를 잘 설명하고 있다. 노드는 기본적인 자료구조에서와 마찬가지로 Root와 Leaf로 구성이 되되고 저장된 값과 질의가 들어온 값을 비교하여 해당되는 노드의 Pointer를 이용하여 넘어간다. 단 Leaf 노드의 경우 마지막 값은 다음 노드를 가리키는데 이용된다. 따라서, B+ 트리가 유지되기 위한 조건은 다음과 같다.

* Leaf 노드는 N/2-1 ~ N-1개의 값을 가져야 한다.
* Root 노드가 Leaf 노드가 아니라면 최소한 2개의 자식을 가져야 한다.
* Root 노드도 Leaf 노드도 아닌 노드는 N/2 ~ N개의 값을 가져야 한다.
(위의 이미지의 경우 N은 4이다.)

위의 조건을 만족하면서 Root 노드에서 출발하여 어떠한 Leaf 노드에 있는 값으로 접근을 한다고 하더라도, 그 깊이가 동일한 결과를 가진다. B+ 트리의 가장 큰 장점은 어떠한 질의가 들어오더라도 어느 정도의 시간이 걸릴지 추측하는 것이 가능하다는 것이다. 하지만 삽입과 삭제의 과정을 거치면서도 위의 조건을 만족시키기 위해 여러 과정을 거치는데 이번 포스팅에서 그 과정까지는 이야기하지 않겠다. 하지만 그 과정을 거치면서도 모든 결과에 대해 동일한 깊이를 유지시키기 위해 노력을 한다는 것이다.
저작자 표시 비영리 변경 금지
신고

'Trash Can' 카테고리의 다른 글

Primary Index - Dense, Sparse  (0) 2011.12.21
Indexing - B+ tree  (2) 2011.12.16
[Java] Single Threaded Execution 예제  (2) 2011.11.10
Thread safe 하지 않은 예제 - Java  (2) 2011.10.27
Thread [Java]  (0) 2011.10.26
Intermediate SQL - cont. 뷰  (0) 2011.10.01
by 가우초 2011.12.16 21:41
| 1 |

티스토리 툴바