B + Tree

B+Tree란:

B-Tree의 확장형으로 B-Tree는 모든 리프 노드에 접근하려면 루트 노드와 모든 브랜치 노드를 방문해야한다. 이러한 단점을 보완하기 위해 B+Tree인덱스가 나왔다.

B+Tree의 특징:

• 모든 자료가 리프노드에 있다.
• 데이터노드의 자료는 정렬되어 있다.
• 모든 리프노드는 같은 레벨에 있다.
• 모든 리프노드는 Linked List로 연결되어 있다.

B+Tree의 장점:

• B+Tree는 리프노드에만 저장하기 때문에 같은 메모리 공간을 할당 받으면 B-Tree보다 더 많은 자식 노드포인터를 가질 수 있음.

• Index Full Scan을 하는 경우 B+Tree는 리프노드끼리 Linked List로 연결되어 있어 리프노드만 순차적으로 탐색할 수 있기 때문에 모든 브랜치 노드를 통해서만 리프 노드에 접근할 수 있는 B-Tree보다 탐색시간이 짧다.

• 특정값을 찾아야하는 상황이라면 리프노드에 모든자료들이 존재하고 그 자료들이 연결리스트로 연결되어 있어 탐색에 있어 매우 유리하다.

결론:

오늘날 데이터베이스에서 가장 중요한 것은 검색 속도이기 때문에 B+Tree구조를 채택하는 경우가 많다.