B-트리 구조와 B+구조

두 가지 모두 데이터베이스 인덱스 구조에서 많이 사용되는 트리 구조입니다.

 

 

B-트리 구조

• M개의 자식을 가질 수 있으며 M차 B트리라고 합니다.
• 각 노드에 포인터와 쌍을 저장하고, 루트 노드에서부터 리프 노드까지 내려가면서 키 값을 찾는 방식입니다.
• 모든 노드가 균등하게 채워져있어 검색 시간이 일정하게 유지됩니다.
• 리프 노드에서 키 값을 찾아야 하기 때문에 B+트리에 비해 데이터를 읽어오는데 더 많은 디스크 I/O가 필요합니다.

 

B+트리 구조

• B-트리 구조와 유사하지만, 리프 노드에만 키와 포인터 쌍을 저장합니다.
• 리프 노드 사이에 연결 리스트를 만들어 빠른 범위 검색 수행이 가능합니다.
• 리프 노드가 모두 같은 깊이에 있다는 점이 B-트리와의 차이점이며, 리프 노드에서 키 값을 찾는 시간이 일정하게 유지
• 범위 검색이 더 뛰어나기에 데이터를 읽어오는데 필요한 디스크 I/O가 적습니다.

즉, B-트리는 빠른 검색 속도를 위해 사용되며, B+트리는 범위 검색과 범위 검색에서의 성능이 우수하기에

데이터베이스 인덱스에 많이 사용됩니다.