[알고리즘] B-tree에 대해 알아보자

B-tree

---

 B-Tree는 데이터베이스와 파일시스템에서 많이 사용하며, RDB 인덱스에서도 일반적으로 B-Tree , B+-Tree 자료구조를 사용한다.

이진 트리의 자식 노드의 개수가 최대 2개라면, B-Tree는 자식 노드의 개수가 2개 이상인 트리이다.

또한 노드 내의 데이터가 1개 이상일 수 있으며, 노드내 최대 데이터 수가 2개라면 2차 B-Tree, 3개라면 3차 B-Tree 라고 한다.

차수가 홀수인지 짝수인지에 따라 알고리즘이 많이 달라진다. 

 

 

B-tree 성립 조건

---

•  노드의 데이터수가 n개라면 자식 노드의 개수는 n+1 개이다.

btree조건 : root 노드의 데이터가 3개(1,2,3)니까 자식 노드의 개수는 4개 이다.

 

https://hyungjoon6876.github.io/jlog/2018/07/20/btree.html

 

• 노드 내 데이터는 반드시 정렬된 상태여야 한다.
• 한 노드의 자식노드에 있는 데이터들은 노드 데이터를 기준으로 데이터보다 작은 값은 왼쪽 서브 트리에 큰값들은 오른쪽 서브 트리에 있어야 한다.
• Root 노드가 자식이 있다면 2개이상의 자식을 가져야 한다.
•  Leaf 노드로 가는 경로의 길이는 모두 같아야 한다. 즉 Leaf 노드는 모두 같은 레벨에 있어야 한다.
• Root 노드를 제외한 모든 노드는 적어도 M/2 개의 데이터를 갖고 있어야 한다.
  즉, 3차 B-Tree 까지는 1개만 가져도 되지만 4차부터는 최소 2개 이상의 데이터를 가져야 한다.(아래 이미지 참고)

 

https://hyungjoon6876.github.io/jlog/2018/07/20/btree.html

참고) B-Tree 삽입/삭제 등 시뮬레이션 해볼 수 있는 사이트

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

 

B-Tree 삽입

---

 

예제를 보면 위에서 명시한 조건들이 성립되는 것을 확인 할 수 있다.

Root 노드를 제외한 모든 노드는 적어도 M/2 개의 데이터를 가지고 있어야 한다. M=4이기 때문에 노드들의 최소 갯수는 4/2=2이다.

또한, leaf 노드는 모두 같은 레벨에 있음을 확인 할 수 있다.

 

B-Tree 삭제

---

삭제는 케이스에 따라 달라지는 것 같아서 추후 추가 예정이다

References

https://hyungjoon6876.github.io/jlog/2018/07/20/btree.html