B tree는 DB인덱스와 관련있는 자료구조이다.
B tree는 BST(이진 탐색 트리)를 일반화한 구조이다.
B tree의 부모 노드는 자녀 노드를 두 개 이상 가질 수 있다.
B tree의 노드가 자녀 x개를 가졌다면 key의 개수는 x-1개이다.
B tree 노드 내 key들은 오름차순으로 저장된다.
B tree 모든 leaf 노드들은 같은 레벨에 있다.
자녀 노드는 최대 두 개 까지 가질 수 있다.
부모노드의 왼쪽 서브트리는 부모의 값보다 작고, 오른쪽 서브트리는 부모의 값보다 크다. 자녀노드를 3개가지고 싶은 경우 값1개로 범위를 지정할 수 없기 때문에, 부모노드에 값을 2개 저장한다.
이진 탐색 트리와 비슷하지만, 자녀 노드의 최대 개수를 입맛에 맞게 결정해서 쓸 수 있다. 자녀 노드가 더 필요한 경우 부모 노드의 데이터 갯수를 추가하여 오름차순 정렬 후 범위에 맞게 자녀 노드들을 구성할 수 있다.
각 노드의 최대 자녀 노드 수
자녀노드가 최대 3개인 경우 3차 B tree
각 노드의 최대 key 수
3차 B tree의 경우 최대 자녀 노드의 수가 3이고, 노드의 key의 갯수는 3-1 = 2이다.
각 노드의 최소 자녀 노드 수
3차 B tree 3/2 = 1.5 올림 ==> 3차 B tree의 경우 자녀 최소 노드의 갯수는 2이다. 단, root node와 leaf node의 경우는 제외한다.
leat node는 자녀가 없는 노드를 뜻하고, root node는 이 규칙의 예외이다.
각 노드의 최소 key 수
단, root node는 제외한다.
위와 같은 트리는 B tree에 존재할 수 없다.
internal 노드의 key 수가 x개라면 자녀의 노드수는 언제나 x+1개다.
key가 2개일 경우 자녀 노드는 3개이고, key가 1개 이면 자녀 노드는 2개이다.
leaf 노드를 제외한, internal 노드는 반드시 key값이 존재하기 때문에 몇차 B tree 인지와 상관없이 internal 노드는 최소 두 개의 자녀를 가진다.
M이 정해지면 root 노드를 제외하고 intenral 노드는 최소 [M/2]개의 자녀 노드를 가질 수 있게 된다.
이진 탐색 트리 : internal 노드의 경우 노드의 수 1개 또는 2개
leaf node의 경우 0개
가운데 key(중간값)
를 기준으로 좌우 key들은 분할
하고 가운데 key는 승진
한다.Key의 최대 개수(M-1) = 2
최소 자녀의 수([M/2]) = 2
key의 최소 개수([M/2]-1) = 1
add(1); add(15); add(2); add(5); add(30); add(90); add(20); add(7);
add(8); add(10); add(50); add(70); add(60); add(40);
★모든 leaf node들은 같은 레벨에 있다 ==> balanced tree
검색 조회시 worst case O(logN)
이진 탐색 트리의 경우 자녀 노드가 0개 ~ 2개 즉, worst case O(N)
탐색 후 leaf node인지 아닌지 알 수 있다. 하지만 B tree는 항상 leaf node들이 같은 level에 존재하기 때문에 시간복잡도가 일정하다.
delete(6); delete(5);
delete(3);
정리 :
delete(7);
delete(2); delete(1);
issue) 어떤 데이터와 바꿔야 하는가? 선임자 또는 후임자
delete(15);
key의 갯수 4개 ==> 5차 B tree
최소 key 갯수 [M/2]-1 ==> 2개
key의 갯수가 1개일때 재조정해야한다.
delete(90); delete(75); delete(45); delete(60);
// 형제 또는 부모의 지원을 받는다.
// 자식노드에 있는 값 가져오면 안된다.