정의
- 모든 리프 노드가 동일한 레벨에 있어 효율적인 검색 및 삽입, 삭제가 가능한 자체 균형 트리
- 이진 트리를 일반화 한 트리
- 이진 트리와 다르게 한 노드에 여러 개의 자식 노드를 가진다(2개 제약 없음)
- 부모 노드도 1개 이상의 키를 가진다.
특징
- balance
- 모든 리프 노드는 같은 레벨에 존재
- 이 특성으로 인해 데이터 크기에 상관없이 일정한 데이터 접근속도 유지
- self balancing
- 데이터 삽입/삭제의 경우 b- tree는 자동적으로 밸런스 유지 작업을 수행
- mulitiple keys per node
- 각 노드마다 여러개의 키를 가질 수 있다.
- 이 특성으로 인해 메모리를 효율적으로 사용하고 트리의 depth을 낮추게 된다.
- order
- b- tree의 key는 정렬된 상태를 유지한다.
- 이 특성으로 트리 검색에 효율적이다.
property
- M : 각 노드의 최대 자녀 노드 수
- 최대 M개의 자녀 노드를 가질 수 있는 B-Tree는 M차 B-tree
- M-1 : 각 노드의 최대 키 개수
- 5차 B-Tree에서 부모 노드의 최대 키는 4개
- ceil(M/2) : 각 노드의 최소 자녀 노드 수
- 5차 B-Tree의 경우, 5/2 = 2.5를 올림한 3이 최소 자녀 노드의 수
- ceil(M/2) - 1 : 각 노드의 최소 키 수
B-Tree 연산
insert
- 데이터 추가는 항상 리프 노드에 한다.
- 삽입 후 노드가 넘치게 되면 가운데 키를 기준으로 좌우 키를 분할하고 가운데 키는 승진한다.
- M차 B-Tree에서 노드 M-1개 보다 더 많은 키가 생기는 경우
delete
- 데이터 삭제는 항상 리프 노드에 한다.
- internal 노드에 데이터가 있는 경우 리프 노드의 데이터와 위치를 교환한 후 진행한다.
- 삭제 후 노드가 최소 키 수 보다 적어진다면 조정 작업을 진행한다.
참고자료
geeksforgeeks- b- tree
깃짱코딩 - [자료구조] B-Tree의 개념, 파라미터, 데이터 삽입, 삭제 과정을 알아보자!