B+ Tree
정의
-
데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드(not Leaf)가 B Tree에 추가로 있음
(기존의 B Tree 와 데이터의 연결리스트로 구현된 색인 구조) -
실제 DB의 인덱싱은 B+ Tree로 이루어져 있습니다.
다음 그림은 인덱싱을 나타낸 것입니다.
다음과 같은 인덱싱을 B+ Tree로 나타내면 아래 그림과 같습니다.
B Tree와 의 차이점
-
모든 key, data가 리프노드에 모여있습니다. B Tree는 리프노드가 아닌 각자 key마다 data를 가진다면, B+ Tree는 리프 노드에 모든 data를 가집니다.
-
모든 리프노드가 연결리스트의 형태를 띄고 있습니다. B Tree는 옆에있는 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+ Tree는 리프노드에서 선형검사를 수행할 수 있어 시간 복잡도가 굉장히 줄어듭니다.
-
리프노드의 부모 key는 리프노드의 첫번째 key보다 작거나 같습니다. 그림의 B+ Tree는 리프노드의 key들을 트리가 가지고 있는 경우여서, data 삽입 또는 삭제가 일어날 때 트리의 key에 변경이 일어납니다. 해당 경우뿐만 아니라 data의 삽입과 삭제가 일어날 때 트리의 key에 변경이 일어나지 않게 하여 더욱 편하게 B+ Tree를 구현하는 방법도 존재하기 때문에 작거나 같다라는 표현을 사용하였습니다.
M차 B+ Tree의 특징
- 노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있습니다.
- 노드에는 최대 M-1개 부터 [M/2]-1개의 키가 포함될 수 있습니다.
- 노드의 키가 x개라면 자식의 수는 x+1개 입니다.
- 최소차수는 자식수의 하한값을 의미하며, 최소차수가 t라면 M = 2t-1을 만족합니다.
장점
-
블럭 사이즈를 더 많이 이용할 수 있음
(key값에 대한 하드디스크 액세스 주소가 없기 때문) -
Leaf 노드끼리 연결 리스트로 연결되어 있어서 범위 탐색에 배우 유리함
단점
- B Tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+ Tree는 무조건 Leaf 노드까지 내려가봐야함
