선발대 과제 인덱스 b-tree, b+tree

b-tree

-한 데이터의 검색은 효율적이나, 모든 데이터를 한번 순회하는데 모든 노드를 방문해야하므로 비효율적이다.

 

b+tree : 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생해서 사용

- 위 b-tree의 단점을 개서니킨 자료구조

- left node를 제외하고 데이터를 저장하지 않아 메모리 확보, 따라서 하나의 노드에 더 많은 포인터를 가질 수 있어 트리높이가 낮아져 검색 속도 향상

- left node끼리 linked list로 연결되어있어 모든 노드 스캔시 시간 절약

 

- 반드시 특정 키에 접근하기 위해 left node까지 가야하는 단점

 

인덱스에 b+tree를 사용하는 이유는 트리의 모양이 항상 균형을 맞춰야하기 때문에 다른 트리보다 높이가 낮아지고 자식들의 밸런스를 잘 유지하면 최악의 경우에도O(logN) 의 시간이 보장된다.  

그리고 left-node끼리 링크드리스트로 연결되어있어 모든 노드 스캔시 시간을 절약할 수 있고, left-node를 제외하고는 데이터를 저장하지 않아 메모리를 확보할 수 있습니다.

 

인덱스는 이진탐색트리도 있지만 이경우는 한곳으로만 쏠릴경우 탐색 시간이 O(N)으로 이진탐색 장점을 가졌다고 보기 어려워졌습니다. 그래서 이것을 보완한 트리중 b-tree가 있습니다. 하지만 b-tree는 순차탐색시 모든 트리를 들려야하기 때문에 비효율적입니다. 그래서 이 순차탐색을 보완하기위해 b+tree가 나왔습니다.

데이터는 left-node에만 있어서 메모리를 확보할 수 있고, left-node는 링크드리스트로 연결되어있고 오름순으로 정렬되어있어 순차탐색시 효율적입니다.