쉬운 코드님의 강의 내용을 정리한 글입니다.
강의가 궁금하시다면, 최하단의 링크를 참고해주세요.
이진 탐색 트리 (BST)는 아래와 같은 특징을 가진다.
- 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가진다.
- 자녀 노드는 최대 두 개까지 가진다.
자녀의 노드 수를 늘릴 수 없을까?
BST 방식을 응용해서 자녀 노드의 값의 범위를 정해 분배해보면 어떨까?
그렇다면 부모 노드에는 2개의 값이 있어야 한다.
이러한 생각들 끝에 B tree 가 등장한다.
B Tree
B tree는 BST를 일반화한 tree 이며, 아래와 같은 형태로 동작 한다.
- 자녀 노드의 최대 개수를 늘리기 위해서 부모 노드에 key를 하나 이상 저장한다.
- 부모 노드의 key들을 오름차순으로 정렬한다.
- 정렬된 순서에 따라 자녀 노드들의 key 값의 범위가 결정된다.
이런 방식을 사용하면 자녀 노드의 최대 개수를 원하는대로 결정해서 쓸 수 있다.
이 때, 최대 몇 개의 자녀 노드를 가질 것인지가 B tree를 사용할 때 중요한 파라미터이다.
B tree의 파라미터
어떤 파라미터를 기준 파라미터로 잡을지 다를 수 있으며, 우리는 M을 기준으로 파라미터들을 알아보자.
-
M : 각 노드의 최대 자녀 노드 수
- 최대 M개의 자녀를 가질 수 있는 B tree → M차 B tree
-
M-1: 각 노드의 최대 key 수
-
[M/2]: 각 노드의 최소 자녀 노드 수 (
[]는 올림 표시)- 이 조건은 root node, leaf node는 제외
-
[M/2] - 1 : 각 노드의 최소 key 수
- root node 제외
B tree의 특징
- internal 노드의 key 수가 x 개라면, 자녀 노드의 수는 언제나 x +1 개다.
- 노드가 최소 하나의 key는 가지기 때문에 몇 차 B tree 인지와 상관 없이 internal 노드는 최소 두 개의 자녀는 가진다.
- M이 정해지면, root 노드를 제외하고 internal 노드는 최소 [M/2] 개의 자녀 노드를 가질 수 있게 된다.
- 모든 leaf 노드들은 같은 레벨에 있다.
- 그래서 B tree를 balanced tree라고 한다.
- 검색 avg/worst case → O(log N)
B tree 데이터 삽입
- 데이터 추가는 항상 leaf 노드에 한다.
- 데이터가 추가 되었을 때, 노드가 넘치면 가운데 (median) key 를 기준으로 좌우 key들은 분할하고 가운데 key는 승진한다.
- 노드가 넘친다는 것은 하나의 노드에서 m-1 보다 더 많은 노드를 가지려는 것을 말한다.
B tree 데이터 삭제
B tree에서의 삭제는 leaf 노드에서 삭제하고 필요하면 재조정하는 방식으로 진행된다.
- 삭제는 항상 leaf 노드에서 수행한다.
- internal 노드의 경우 선임자와 위치 바꾼 후 삭제한다.
- 삭제 후 최소 Key 수보다 적어졌다면 재조정한다.
- 형제 지원 → 부모 지원 받고 형제 합침 → 부모 도움 후 부모도 문제 시 재차 조정
- 삭제도 항상 leaf 노드에서 발생한다.
- 삭제 후 최소 key 수보다 적어졌다면 재조정한다.
- key 수가 여유있는 형제의 지원을 받는다.
- 1번이 불가능하면 부모의 지원을 받고 형제와 합친다.
- 2번 후 부모에 문제가 있다면 거기서 다시 재조정한다.
참고: B tree에서 각 노드의 최소 key 수는 [M/2] - 1 으로 계산 (루트 노드는 제외하고)
삭제 후 최소 키 보다 적다면
- key 수가 여유있는 형제의 지원을 받는다.
- 왼쪽 형제(동생)가 여유 있으면, 동생의 가장 큰 key를 부모 노드의 나와 동생 사이에 둔다. 원래 그 자리에 있던 key는 나의 가장 왼쪽에 둔다.
- 왼쪽 형제에 여유가 없고, 오른쪽 형제(형)가 여유있다면, 형의 가장 작은 key를 부모 노드의 나와 형 사이에 둔다. 원래 그 자리에 있던 key 는 나의 가장 오른쪽에 둔다.
- 1번이 불가능하면 부모의 지원을 받고 형제와 합친다.
- 동생이 있으면 동생과 나 사이의 key를 부모로 부터 받는다. 그 key와 나의 key를 차례대로 동생에게 합친다. 나의 노드를 삭제한다.
- 동생이 없으면 형과 나 사이의 key를 부모로 부터 받는다. 그 key와 형의 key를 차례대로 나에게 합친다. 형의 노드를 삭제한다.
- 부모가 지원한 후 부모에 문제가 있다면 상황에 맞게 대응한다.
- 부모가 root 노드가 아니라면 그 위치에서 부터 다시 1번부터 재조정을 시작한다.
- 부모가 root 노드고 비어있다면 부모 노드를 삭제한다. 직전에 합쳐진 노드가 root노드가 된다.
internal 노드 데이터 삭제
- internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제한다.
- leaf 노드에 있는 데이터 중에 어떤 데이터와 위치를 바꿔줄 것인지가 이슈
- 선임자나 후임자는 항상 leaf 노드에 있으므로 삭제할 데이터의 선임자(predecessor)나 후임자(successor)와 위치를 바꿔준다.
- 선임자(predecessor): 나보다 작은 데이터들 중 가장 큰 데이터
- 후임자(successor): 나보다 큰 데이터들 중 가장 작은 데이터
B tree에 데이터를 삽입하고 삭제하는 방식은 다른 방식도 있다는 것을 참고할 것!
B tree 와 DB 인덱스
왜 B tree 계열이(B+ tree, B* tree ...) 인덱스에 사용될까?
- 모든 경우(avg, worst case / 조회, 삽입, 삭제)에서 시간복잡도가 O(logN) 이다.
- BST노드는 자녀노드 2개만 가능하다(key 가 1개)
하지만 AVL tree, Red-Black tree 등의 self-balancing BST가 존재한다. 이 BST들도 시간 복잡도는 똑같이 O(logN)이다. 그럼에도 왜 B tree를 사용할까?
이유를 알기 위해서 컴퓨터 시스템에 대해 알아야 한다.
Computer system
- CPU: 프로그램 코드가 실제로 실행되는 곳
- Main memory(RAM): 실행중인 프로그램의 코드들과 실행에 필요한 데이터와 결과 데이터들이 상주
- Secondary storage(SSD or HDD): 프로그램과 데이터가 영구적으로 저장되는 곳.
- 실행중인 프로그램 데이터가 일부 임시 저장되는 곳(swap)
- DB가 저장되는 곳
- 데이터 처리 속도 느림
- 데이터 저장 용량 가장 큼
- Block 단위로 읽고 쓴다
참고: 저장 공간 중 RAM, SSD, HDD 순으로 속도가 빠르다.
DB 는 Secondary storage에 저장된다. 즉, 데이터를 조회하기 위해 Secondary storage에 접근해야한다. 하지만 Secondary storage는 처리 속도가 느리기 때문에 최대한 적게 접근하는 것이 성능적으로 좋다. 또한 Block 단위로 읽고 쓰는 Secondary storage 는 연관된 데이터를 모아서 저장하면 효율적이다.
이러한 이유로 BST가 아닌 B tree 계열을 인덱스에 사용하는 것!
참고 자료
(1부) B tree의 개념과 특징, 데이터 삽입이 어떻게 동작하는지를 설명합니다! (DB 인덱스과 관련있는 자료 구조)
