[자료구조] B+ Tree
August 07, 2022
B+Tree
DB에서 널리 사용되는 트리 자료구조의 일종으로, 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리구조가 B트리입니다. 이와 비슷한 B+트리는 모든 레코드들이 트리의 최하위 레벨에 정렬되어 있고 오직 키들만 내부 블록에 저장됩니다. 리프노드를 연결리스트 형태로 연결한 트리이며 최대 key 개수가 정해져있다는 특징이 있습니다. 검색에 필요한 I/O 동작 횟수를 줄일 수 있다는 장점이 있습니다.
검색
단일 노드의 대소관계만 비교했던 이진트리와 달리 어느 범위에 속하는지를 판단합니다.
한 노드에는 key가 정해진 key의 개수 이하만큼 들어있습니다.
만약 key의 개수 = 2이며 a, b가 있다면 검색된 x key가x < a, a < x < b, b < x 인지 범위를 판단하며 탐색합니다.
삽입
일반적인 경우 검색로직과 같습니다.
x key가 x < a, a < x < b, b < x 인지 범위를 판단하며 탐색합니다. 최종적으로 빈 노드에 삽입 후 부모 key를 삽입된 key로 갱신합니다.
하지만, 최대 key 개수를 초과했을 때 분할을 거칩니다.
분할
이미 key의 개수 = 2이고 a, b가 있는 노드에 x가 삽입된다면 분할 과정을 거칩니다.
중앙값을 부모로 올리고 범위에 맞게 노드를 재배치합니다. 여기선 예시를 덧붙이겠습니다.
// key의 개수는 2이지만 [1, 2, 3] 세 개가 된 상태이며 편의상 전체 트리가 아닌 일부를 표현
[4, 6] //parent
[1, 2, 3], [5], [7] //child
(left ), (mid), (right)
// i) 중앙값 2를 올린다. 이 때 3은 2보다 크므로 2와 4의 사이로 들어간다.
[2, 4, 6]
[1], [3], [5], [7]
// ii) 반복한다.
[4]
[2], [6]
[1], [3], [5], [7]삭제
삭제는 세 경우가 있습니다.
- 리프노드: 빈 key를 부모에서 가져온다.
- 중간노드: 자식이 끊길경우 다른자식으로 병합 후 분할한다.
- 루트노드: 가장 가까운 자식(left의 최대 또는 right의 최소)와 교체한 뒤 리프노드가 된 루트노드를 삭제한다.
