B+ Tree | Notion

B트리와 굉장히 유사하지만 다른점이라고 하면 리프노드는 연결리스트의 형태를 띄어 선형 검색이 가능하다는 점이다. 이러한 특징점 때문에 굉장히 작은 시간복잡도에 검색을 수행할 수 있다. B트리와 B+트리의 차이점 위주로 공부해보자.

B+Tree

실제 DB의 인덱싱은 B+트리로 이루어져있다. 다음 그림은 인덱싱을 나타낸 것이다. 인덱싱은 어떠한 자료를 찾는데 key값을 이용해 효과적으로 찾을 수 있는 기능이다.

다음과 같은 인덱싱을 B+트리로 나타내면 아래 그림과 같다.

B+트리에는 리프노드에 새로운 data값들이 들어가 있다. B트리의 경우에는 편의상 data를 생략하여 그렸지만, 각 key값이 data를 가지고 있었다고 생각하면 된다. 그럼 B트리와 B+트리 달라진 점에 대해서 알아보자.

모든 key, data가 리프노드에 모여있다. B트리는 리프노드가 아닌 각자 key마다 data를 가진다면, B+트리는 리프 노드에 모든 data를 가진다.
모든 리프노드가 연결리스트의 형태를 띄고 있다. B트리는 옆에있는 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+트리는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 굉장히 줄어든다.
리프노드의 부모 key는 리프노드의 첫번째 key보다 작거나 같다. 그림의 B+트리는 리프노드의 key들을 트리가 가지고 있는 경우여서, data 삽입 또는 삭제가 일어날 때 트리의 key에 변경이 일어난다. 해당 경우뿐만 아니라 data의 삽입과 삭제가 일어날 때 트리의 key에 변경이 일어나지 않게 하여 더욱 편하게 B+트리를 구현하는 방법도 존재하기 때문에 작거나 같다라는 표현을 사용한다.

B트리와 같이 M차 B+트리는 다음과 같은 특징을 같는다.

노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있다.
노드에는 최대 M−1개 부터 [M/2]−1개의 키가 포함될 수 있다.
노드의 키가 x개라면 자식의 수는 x+1개이다.
최소차수는 자식수의 하한값을 의미하며, 최소차수가 t라면 M=2t−1을 만족한다. (최소차수 t가 2라면 3차 B트리이며, key의 하한은 1개이다.)

모든 설명의 과정은 리프노드가 삽입 또는 삭제 될 때 트리의 key가 변경되는 경우로 진행한다. 검색과정은 B트리와 동일하기 때문에 생략하고 삽입의 과정부터 시작해본다. 삽입의 과정도 B트리와 매우 유사하지만 리프노드에서 최대 key개수를 초과할 때가 다르다.

B트리와 똑같은 삽입 과정을 수행한다.