B+트리, B트리 비교

B+트리란?

B트리에서 확장된 개념으로, 리프 노드에만 실제 데이터를 담는다

B+트리는 리프 노드에만 데이터를 저장하고, 내부 노드에는 데이터가 아닌 키만을 저장한다

키는 데이터를 찾기 위한 인덱스 역할을 하며, 실제 데이터는 리프 노드에서만 접근 가능

이로 인해 모든 데이터 접근이 리프 노드에서 이루어지며, 데이터가 정렬된 형태로 연결되어 있다

B+트리는 리프 노드를 순차적으로 연결하는 포인터 집합을 가지고 있다.

인덱스된 순차 파일 처리시,

포인터를 이용하여, `키 : 값`을 일일이 비교하지 않고 다음 데이터에 접근해서 빠르게 처리할 수 있다.
(이부분 무슨 말인지 이해가 안된다, 다시 알아보자)

 

https://en.wikipedia.org/wiki/B%2B_tree#/media/File:Bplustree.png

 

 

데이터 삽입

처음 1,2가 노드에 들어있을때

3을 추가하면

 

노드의 최대 키을 초과하여( 3차이기 때문에 키는 2개가 최대이다)

중간에 있는값 2 를 부모노드로 승격시킨다

근데 이때 b트리와 다른점은 데이터는 리프에서만 접근하기 때문에

부모노드로 2를 올려도 리프에 2가 계속 남아있어야한다

부모노드의 2는 탐색키 역활이다.(3을 찾고 싶을때 이것이 2보다 큰지 작은지 따지는 용도)

 

또 5를 추가하면 
2보다 크기 때문에 [2,3]이 있는 노드에 5를 추가하고
[2,3,5]가 되기 때문에 중간의 3을 부모노드에 추가하고 [2],[3,5]로 리프노드를 분할 하게된다

데이터 삭제

*경우의 수가 다양하다고한다

 

여기서 2를 삭제한다고 하면

리프노드에서 2를 제거하고
근데 노드의  최소 키보다 작아지기 때문에

형제 노드에서 3을 빌려온다

그리고 부모노드를 알맞게 정리한다

 

 

B트리 vs B+트리

 

특성	B-트리	B+트리
데이터 저장 위치	키와 데이터를 같은 노드에 저장	데이터는 리프 노드에만 저장
범위검색	상대적으로 비효율적	매우 효율적
단일 키 검색	더 빠를 수 있음	약간 느릴 수 있음
삽입/삭제	간단	리프 노드에서 주로 작업, 포인터 조정 필요

• b+트리가 범위 검색에 좋은 이유 : 연속적 접근이 가능 하기 때문에,
  리프 노드의 시작점만 찾으면 나머지는 연결된 노드를 따라가며 데이터를 빠르게 읽을 수 있습니다.
  (예: id BETWEEN 10 AND 50)

 

여기서 삽입 삭제 해볼 수 있음

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html