indexed-sequential file들은 인덱스를 통해 정렬된 레코드에 접근할 수 있다. 하지만 이러한 파일구조는 파일의 크기가 커질수록(레코드의 수가 많아질 수록) 누적된 Insert와 Delete연산으로 인해 많은 오버플로우 블록이 만들어져 전체적인 성능이 떨어지고, 때문에 주기적으로 인덱스 파일을 재구성하여 오버플로우 블록을 정리해야할 필요가 있다. 이런 문제를 해결하기 위해 대부분의 주요 DBMS에서는 B+트리 인덱스를 사용하여 조회 성능을 높인다.
B+- tree는 Multilevel index의 한 종류로,
- root node와 internal node에는 split value와 하위 노드로의 포인터만 존재 (Sparse Index)
- leaf node에는 각 레코드의 search key값과 레코드로의 포인터가 존재 (Dense Index)
- 레코드의 물리적 위치는 leaf node에만 저장되기 때문에 항상 leaf node에서 탐색 종료
- root node -> internal node -> leaf node -> record 순
- root node는 최소 2개의 children
n차 B+트리의 각 노드들은 총 n개의 포인터(P)와 n-1개의 키(K)로 구성된다. 각 포인터는 하위노드 혹은 레코드의 물리적 주소를 가리키고, 한 노드 안의 모든 키값은 순서대로 정렬되어있다.
non-leaf node
non-leaf node에서의 key는 split value의 역할을 하고, split value와 같거나 큰 키값은 오른쪽 포인터를 따라가기 때문에 non-leaf 노드에서는 첫번째 포인터를 제외한 나머지 값들이 키-포인터 쌍을 이룬다. 이때 포인터는 하위노드를 가리킨다. 즉, 위의 사진에서 Pn-1은 Kn-2보다 크거나 같고 Kn-1보다 작은 search key들이 있는 노드를 가리키는 포인터이다.
.
insertion과 deletion은 O(logN)
FIND
B-Tree
B+트리 인덱스의 원형으로, leaf node 뿐만 아니라 root node와 internal node에서도 레코드를 가리키는 포인터를 가지고있어서 트리에 키가 중복되어 저장되는 것을 막은 인덱스이다. B트리의 leaf node는 B+트리와 같고, non-leaf node에는 각 키값마다 하나의 포인터 B이 추가되었다. 이는 해당 키에 대응하는 레코드를 가리키는 포인터로, 여기에서 키값은 split value이면서 동시에 search key의 역할을 한다.
B+ -Tree VS B-Tree
B 트리
- 장점:
- 모든 노드에 데이터가 포함될 수 있으므로, 특정 데이터에 도달하기 위해 리프 노드까지 도달할 필요가 없다
- 균형 트리로 유지되므로 삽입, 삭제, 검색의 시간 복잡도가 일정하게 유지된다.
- 단점:
- 모든 노드에 데이터를 저장하기 때문에 공간 사용이 비효율적
- 범위 검색 시, 리프 노드 간의 연결이 없으므로 비효율적
B+ 트리
- 장점:
- 리프 노드 간의 연결로 인해 범위 검색 및 순차 접근이 효율적
- 데이터가 리프 노드에만 저장되므로, 내부 노드의 메모리 사용이 줄어들고, 트리의 높이가 낮아질 수 있다
- 데이터베이스에서 일반적으로 사용되는 구조로, 대량의 데이터를 다루는 데 최적화
- 단점:
- 모든 데이터 접근이 리프 노드를 통해 이루어져야 하므로, 때때로 추가적인 경로를 거쳐야 할 수 있다
- 리프 노드의 연결 리스트 유지 관리가 필요
- B 트리는 데이터를 모든 노드에 저장하며 균형 트리로서 일정한 시간 복잡도를 유지합니다. 이는 특정 데이터를 찾는 데 효율적
- B+ 트리는 데이터를 리프 노드에만 저장하고 내부 노드는 오직 키와 포인터만 가지며, 리프 노드 간의 연결로 인해 범위 검색과 순차 접근에 매우 효율적