# B 트리 & B+ 트리 (B-Tree & B+Tree)
# B & B+ 트리가 왜 필요할까?
원인
이진 트리는 하나의 부모가 두 개의 자식밖에 가지지 못하고, 균형이 맞지 않으면 검색 효율이 선형 검색 급으로 떨어집니다.
하지만 이진 트리 구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN)의 성능을 보이는 장점이 있기 때문에 계속 개선시키기 위한 노력이 이루어지고 있습니다.
- 균형이진트리는 트리의 높이를 균형적으로 유지시키기에 검색 시,
O(logN)의 안정성을 유지합니다. - B & B+ 트리는 균형이진탐색트리의 일종입니다.
# B Tree
- 이진 트리와는 다르게 하나의 노드에 많은 정보를 가질 수 있습니다.
- 이진 트리를 확장해서, 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것이 B Tree입니다.
- 데이터베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종입니다.
- 자식 수에 대한 일반화를 진행하면서, 하나의 레벨에 더 저장되는 것 뿐만 아니라 트리의 균형을 자동으로 맞춰주는 로직까지 갖추고 있습니다.
# B Tree의 특징
- 노드의 자료수가 N이면, 자식 수는 N+1이어야 한다.
- 각 노드의 자료는 정렬된 상태여야 한다.
- 루트 노드는 적어도 2개 이상의 자식을 가져야 한다.
- 루트 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다.
- 외부 노드로 가는 경로의 길이는 모두 같다.
- 입력 자료는 중복될 수 없다.
# B Tree의 검색 과정
- 루트 노드에서 시작하여 key들을 순회하면서 검사합니다.
- 만일 k와 같은 key를 찾았다면 검색을 종료합니다.
- 검색하는 값과 key들의 대소관계를 비교해봅니다. 어떠한 key들 사이에 k가 들어간다면 해당 key들 사이의 자식노드로로 내려갑니다.
- 해당 과정을 리프노드에 도달할 때까지 반복합니다. 만일 리프노드에도 k와 같은 key가 없다면 검색을 실패합니다.
# B Tree의 삽입 과정
- 트리가 비어있으면 루트 노드를 할당하고 k를 삽입합니다.
- 만일 루트노드가 가득 찼다면, 노드를 분할하고 리프노드가 생성됩니다.
- 이후부터는 삽압하기에 적절한 리프노드를 찾아 k를 삽입합니다.
- 삽입위치는 노드의 key값과 k값을 검색 연산과 동일한 방법으로 비교하면서 찾습니다.
# 분할이 일어나지 않는 경우
- 리프노드가 가득차지 않았다면, 오름차순으로 k를 삽입합니다.
# 분할이 일어나는 경우
- 오름차순으로 요소를 삽입합니다.
- 노드가 담을 수 있는 최대 key 개수를 초과하게 됩니다.
- 중앙값에서 분할을 수행합니다.
- 중앙값은 부모 노드로 병합하거나 새로 생성됩니다.
- 왼쪽 키들은 왼쪽 자식으로, 오른쪽 키들은 오른쪽 자식으로 분할됩니다.
- 부모 노드를 검사해서 또 다시 가득 찼다면, 다시 부모노드에서 위 과정을 반복합니다.
# B Tree의 삭제 과정
- 요소를 삭제하기 위해선
1. 삭제할 키가 있는 노드 검색,2. 키 삭제,3. 필요한 경우, 트리 균형 조정을 해야합니다.
# 삭제할 key k가 리프에 있는 경우
# 현재 노드의 key 개수가 최소 key 개수보다 크다면
# 왼쪽 또는 오른쪽 형제 노드의 key가 최소 key 개수 이상이라면
# 왼쪽, 오른쪽 형제 노드의 key가 최소 key 개수이고, 부모노드의 key가 최소개수 이상이면
# 삭제할 key k가 내부 노드에 있고, 노드나 자식에 키가 최소 키수보다 많을 경우
# 삭제할 key k가 내부 노드에 있고, 노드에 key 개수가 최소key 개수만큼, 노드의 자식 key 개수도 모두 최소 key 개수인 경우
참고
B Tree 직접 생성해보기
https://www.cs.usfca.edu/~galles/visualization/BTree.html (opens new window)
# B+ Tree
- 데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드(not Leaf)가 추가로 있습니다.
- (기존의 B-Tree와 데이터의 연결리스트로 구현된 색인구조)
- B-Tree의 변형 구조로, index 부분과 leaf 노드로 구성된 순차 데이터 부분으로 이루어집니다.
- 인덱스 부분의 key 값은 leaf에 있는 key 값을 직접 찾아가는데 사용합니다.
- 모든 key, data가 리프노드에 모여있습니다.
- B트리는 리프노드가 아닌 각자 key마다 data를 가진다면, B+트리는 리프 노드에 모든 data를 가집니다.
- 모든 리프노드가 연결리스트의 형태를 띄고 있습니다.
- B트리는 옆에있는 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+트리는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 굉장히 줄어듭니다.
- 리프노드의 부모 key는 리프노드의 첫번째 key보다 작거나 같습니다.
- 그림의 B+트리는 리프노드의 key들을 트리가 가지고 있는 경우여서, data 삽입 또는 삭제가 일어날 때 트리의 key에 변경이 일어납니다.
# 예시
- 실제 DB의 인덱싱은 B+트리로 이루어져있습니다.
- 인덱싱은 어떠한 자료를 찾는데 key값을 이용해 효과적으로 찾을 수 있는 기능입니다.
# B+ Tree의 삽입 과정
- 삽입의 과정도 B트리와 매우 유사하지만 리프노드에서 최대 key개수를 초과할 때가 다릅니다.
# 분할이 일어나지 않고, 삽입 위치가 리프노드의 가장 앞 key 자리가 아닌 경우
- B트리와 똑같은 삽입 과정을 수행합니다.
# 분할이 일어나지 않고, 삽입 위치가 리프노드의 가장 앞 key 자리인 경우
- 삽입 후 부모 key를 삽입된 key로 갱신하고, data를 넣어줍니다.
# 분할이 일어나는 삽입과정
- 분할이 일어나는 노드가 리프노드가 아니라면 기존 B트리와 똑같이 분할을 진행합니다.
- 중간 key를 부모 key로 올리고, 분할한 두개의 노드를 왼쪽, 오른쪽 자식으로 설정합니다.
- 분할이 일어나는 노드가 리프노드라면 중간 key를 부모 key로 올리지만, 오른쪽 노드에 중간 key를 포함하여 분할합니다.
- 또한 리프노드는 연결리스트이기 때문에 왼쪽 자식노드와 오른쪽 자식 노드를 이어줘 연결리스트 형태를 유지합니다. 해당 부분이 B트리의 분할과 다른 점입니다.
# B+ Tree의 삭제 과정
# 삭제할 key k가 index에 없고, 리프노드의 가장 처음 key가 k가 아닌경우
# 삭제할 key k가 리프노드의 가장 처음 key인 경우
- 먼저 리프노드의 k를 삭제하는 과정을 수행합니다.
- key의 개수가 최소 key의 개수라면 B트리의 삭제 과정 중 형제노드의 key를 빌려오는 경우나 부모key와 병합하는 등 과정들은 동일하게 수행합니다.
- 단, 리프노드가 병합할 때는 부모key와 오른쪽 자식의 처음 key가 동일하기 때문에 부모key를 가져오는 과정만 생략하고 왼쪽 자식과 오른쪽 자식을 병합만 하면 됩니다.
- 리프노드의 k를 삭제한 후, index내의 k를 inorder successor로 변경합니다.
# B+ Tree의 장단점
# 장점
- 블럭 사이즈를 더 많이 이용할 수 있음 (key 값에 대한 하드디스크 액세스 주소가 없기 때문)
- leaf 노드끼리 연결 리스트로 연결되어 있어서 범위 탐색에 매우 유리함
# 단점
- B-tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+tree는 무조건 leaf 노드까지 내려가봐야 함
참고
B+ Tree 직접 생성해보기
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html (opens new window)
# B-Tree & B+ Tree 요약
TIP
B-tree는 각 노드에 데이터가 저장됩니다.
B+tree는 index 노드와 leaf 노드로 분리되어 저장됩니다.
(또한, leaf 노드는 서로 연결되어 있어서 임의접근이나 순차접근 모두 성능이 우수함)
- B-tree는 각 노드에서 key와 data 모두 들어갈 수 있고, data는 disk block으로 포인터가 될 수 있습니다.
- B+tree는 각 노드에서 key만 들어감. 따라서 data는 모두 leaf 노드에만 존재합니다.
- B+tree는 add와 delete가 모두 leaf 노드에서만 이루어집니다.