B tree
이진 탐색 트리(BST)의 발전된 형태로, 자녀 노드의 최대 개수를 원하는대로 결정할 수 있는 구조
- 특징
-
자녀 노드의 최대 개수를 늘리기 위해 부모 노드에 key를 하나 이상 저장한다.
-
부모 노드의 key들을 오름차순으로 정렬한다.
-
정렬된 순서에 따라 자녀 노드들의 key값의 범위가 결정된다.
-
internal 노드의 key 수가 x개라면 자녀의 노드 수는 언제나 x + 1 이다.
따라서 최대 몇 개의 자녀 노드를 가질 것인지가 B tree를 사용할 때 중요한 파라미터가 됨!
- 파라미터 종류
M: 각 노드의 최대 자녀 노드 수
ex) 최대 M개의 자녀를 가질 수 있는 B tree를 M차 B tree라고 부른다.
M-1: 각 노드가 가질 수 있는 최대 key 수
「M/2￢: 각 노드의 최소 자녀 노드 수(root노드와 leaf노드는 제외)
「M/2￢-1: 각 노드의 최소 key 수(root노드 제외)
B tree 데이터 삽입
항상 leaf 노드에서 오름차순으로 하고 노드가 넘치면 가운데 key를 기준으로 좌우 key들은 분할하고 가운데 key는 부모노드로 승진한다.
모든 leaf 노드들이 같은 레벨에 있기 때문에 balanced tree라고 말할 수 있음.(BST같은 경우 자식들이 하나로만 뻗어 내려갈 수 있기 때문에 balanced tree는 아님)
B tree에서 검색할 때 평균과 최악의 경우 둘 다 O(logN)이기 때문에 일정한 성능을 낼 수 있음.
B tree 데이터 삭제
항상 leaf 노드에서 발생하고 삭제 후 최소 key 수보다 적어졌다면 재조정한다
* 「M/2￢-1 : 각 노드의 최소 key 수(root노드 제외)
- 재조정 과정
- key 수가 여유있는 형제의 지원을 받는다.(형제가 같은 key 수를 가지고 있다면 동생(왼쪽 형제)의 지원이 우선)
동생의 가장 큰 key를 부모 노드의 나와 동생 사이에 두고 원래 그 자리에 있던 key는 나의 가장 왼쪽에 둔다. - 1번이 불가능하다면 부모의 지원을 받고 왼쪽 형제와 합친다.
동생이 있으면 동생과 나 사이의 key를 부모로 부터 받고 그 key와 나의 key를 차례대로 동생에게 합친 후 나의 노드를 삭제한다. - 2번 후 부모에 문제가 있다면 부모 위치에서 다시 재조정한다.
다시 1번부터 재조정 과정을 거치고 부모가 root 노드고 비어있다면 부모 노드를 삭제하고 직전에 합쳐진 노드가 root 노드가 된다
internal 노드 데이터 삭제
: internal 노드에 있는 데이터를 삭제하려면 leaf노드에 있는 데이터와 위치를 바꾼 후 삭제.
어떤 leaf 노드의 데이터와 위치를 바꿔줄 것인지가 이슈.
=> 삭제할 데이터의 선임자나 후임자와 위치를 바꿔준다.(B tree의 특성을 해치지 않기 위함)
* 선임자 : predecessor, 나보다 작은 데이터들 중 가장 큰 데이터
* 후임자 : successor : 나보다 큰 데이터들 중 가장 작은 데이터
트리의 구조를 잘 생각해보면 선임자나 후임자는 항상 leaf노드에 있게 됨.
왜 DB index로 B tree 계열이 사용되는가?
