[DB]B+TREE

B+TREE

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

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

장점

블럭 사이즈를 더 많이 이용할 수 있음 (key 값에 대한 하드디스크 액세스 주소가 없기 때문)

leaf 노드끼리 연결 리스트로 연결되어 있어서 범위 탐색에 매우 유리함

단점

B-tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+tree는 무조건 leaf 노드까지 내려가봐야 함

📝참고 블로그 : https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Plus-Tree