1. 개요

B+Tree이란?

DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조이다.

데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드(not Leaf)가 추가로 있다.

<aside> 💡 모든 노드에 데이터를 저기존의 B-Tree와 데이터의 연결리스트로 구현된 색인구조 기존의 B-트리 + 데이터의 연결 리스트

</aside>

B+Tree = Index node + Data node

• Index node : leaf node를 제외한 나머지 node들
• Data node : leaf node를 일컫는 동의어

특징

• 리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.
• 리프노드들은 LinkedList로 연결되어 있다.
• 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.

이용